class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
n = len(arr)
for i in range(n - m * k + 1):
t = True
for s in range(m):
for t in range(k):
if arr[i + s] != arr[i + s + t * m]:
t = False
break
if not t:
break
if t:
return True
return False


class Solution:
def getMaxLen(self, nums: List[int]) -> int:
pos = [-1, -2]
s = c = 0
ans = 0
for i, n in enumerate(nums):
if n == 0:
pos = [i, -2]
s = c = 0
elif n < 0:
c = (c + 1) % 2

if c == 1 and pos[1] == -2:
pos[1] = i
ans = max(ans, i - pos[c])
return ans


class Solution:
def minDays(self, grid: List[List[int]]) -> int:

def conv(arr):
ans = 0
for n in arr:
ans = 2 * ans + n
return ans

init = tuple(conv(arr) for arr in grid)
n, m = len(grid), len(grid[0])

def conv_r(v):
ans = []
for _ in range(m):
ans.append(v & 1)
v //= 2
return ans

def floodfill(grid, i, j):
for x, y in [(i+1, j), (i-1,j), (i, j+1), (i, j-1)]:
if x < 0 or y < 0 or x >= n or y >= m or grid[x][y] == 0:
continue
grid[x][y] = 0
floodfill(grid, x, y)

def count(arr):
grid = [conv_r(v) for v in arr]
ans = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
ans += 1
if ans > 1:
return ans
grid[i][j] = 0
floodfill(grid, i, j)
return ans

if count(init) != 1:
return 0
p = 0
stack = [(init, 0)]
visited = {init}
while p < len(stack):
cur, s = stack[p]

for i in range(n):
for j in range(m):
if (cur[i] >> j) & 1:
v = cur[i] ^ (1 << j)
new = cur[:i] + (v, ) + cur[i+1:]
if new not in visited:
if count(new) != 1:
return s + 1
stack.append((new, s+1))
p += 1
return -1


class Solution:
def numOfWays(self, nums: List[int]) -> int:

M = 10 ** 9 + 7

def C(a, b):
ans = 1
for k in range(1, b + 1):
ans *= (a - k + 1)
ans //= k
#ans %= M
return ans % M

def f(nums):
n = len(nums)
if n <= 2:
return 1

smaller = [v for v in nums[1: ] if v < nums[0]]
bigger = [v for v in nums[1: ] if v > nums[0]]

left = f(smaller)
right = f(bigger)

return left * right * C(len(smaller) + len(bigger), len(smaller)) % M

return f(nums) - 1