class Solution:
def buildArray(self, target: List[int], n: int) -> List[str]:
ret = []
cur = 0
for t in target:
ret.extend(["Push", "Pop"] * (t - cur - 1))
ret.append("Push")
cur = t
return ret


sum(i, j) = arr[i] ^ arr[i+1] ^ .. ^ arr[j],

int countTriplets(int* arr, int arrSize){
int s[301];
s[0] = 0;
for (int i = 0; i < arrSize; i ++)
s[i + 1] = s[i] ^ arr[i];
int ret = 0;
for (int i = 0; i < arrSize; i ++) {
for (int k = i + 1; k < arrSize; k ++) {
for (int j = i + 1; j <= k; j ++) {
int a = s[j] ^ s[i];
int b = s[k+1] ^ s[j];
ret += a == b;
}
}
}
return ret;
}


class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:

children = [[] for _ in range(n)]
for p, c in edges:
children[p].append(c)

def collect(root):
ans = 0
for child in children[root]:
t = collect(child)
ans += t
if t or hasApple[child]:
ans += 2
return ans

return collect(0)


dp(i, j, k) += dp(ic+1, j, k-1)

class Solution:
def ways(self, pizza: List[str], k: int) -> int:
MOD = 10 ** 9 + 7
n, m = len(pizza), len(pizza[0])
s = [[0] * (m + 1) for _ in range(n + 1)]
for i, row in enumerate(pizza):
for j, c in enumerate(row):
s[i][j] = s[i - 1][j] + s[i][j - 1] + (c == 'A') - s[i-1][j-1]
def get(i, j, x, y):
return s[x][y] - s[x][j-1] - s[i-1][y] + s[i-1][j-1]

memo = {}
def dp(i, j, k):
if i >= n or j >= m:
return 0
if k == 1:
return 1 if get(i, j, n-1, m-1) > 0 else 0
if (i, j, k) in memo:
return memo[i, j, k]
ans = 0
for ic in range(i, n):
if get(i, j, ic, m-1) > 0:
ans = (ans + dp(ic+1, j, k-1)) % MOD
for jc in range(j, m):
if get(i, j, n-1, jc) > 0:
ans = (ans + dp(i, jc+1, k-1)) % MOD
memo[i, j, k] = ans
return ans

return dp(0, 0, k)