Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        for j in range(P):
            X[j] = (X[j] - C(j) * pow(-i, P-1-j, P)) % P
        X[0] = (X[0] + 1) % P
print(*X)


Fixed submission:
P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        c = 1
        for j in range(P)[::-1]:
            X[j] = (X[j] - C(j) * c) % P
            c = -c * i % P
        X[0] = (X[0] + 1) % P
print(*X)

Buggy python submission (verdict: Time Limit Exceeded):
P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        for j in range(P):
            X[j] = (X[j] - C(j) * pow(-i, P-1-j, P)) % P
        X[0] = (X[0] + 1) % P
print(*X)


Fixed submission:
P = int(input())
A = [int(a) for a in input().split()]
X = [0] * P
fa = [1]
for i in range(1, P):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, P)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]
def C(i):
    return fa[P-1] * fainv[i] * fainv[P-1-i] % P

for i in range(P):
    if A[i]:
        c = 1
        for j in range(P)[::-1]:
            X[j] = (X[j] - C(j) * c) % P
            c = -c * i % P
        X[0] = (X[0] + 1) % P
print(*X)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left as bl
N = int(input())
P = 998244353
NN = 17
XX = [0] * (2**(NN+1)-1)
pow2 = [1]
for _ in range(1, 202020):
    pow2.append(pow2[-1]*2%P)

def addvalue(j):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += 1
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

X = []
Y = []
XY = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append((x, y))

X = sorted(X)
Y = sorted(Y)
XY = sorted(XY, key = lambda x: x[1])

DX = {}
for i in range(N):
    DX[X[i]] = i

ans = 0
U = 0
for x, y in XY:
    a = rangesum(0, DX[x])
    L = bl(X, x)
    b = U-a
    d = L-a
    c = N-a-b-d-1
    ans = (ans + pow2[N] - (pow2[a+b] + pow2[b+c] + pow2[c+d] + pow2[d+a] - pow2[a] - pow2[b] - pow2[c] - pow2[d] + 1)) % P
    U += 1
    addvalue(DX[x])
    
print(ans)


Fixed submission:
from bisect import bisect_left as bl
N = int(input())
P = 998244353
NN = 18
XX = [0] * (2**(NN+1)-1)
pow2 = [1]
for _ in range(1, 202020):
    pow2.append(pow2[-1]*2%P)

def addvalue(j):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += 1
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

X = []
Y = []
XY = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    XY.append((x, y))

X = sorted(X)
Y = sorted(Y)
XY = sorted(XY, key = lambda x: x[1])

DX = {}
for i in range(N):
    DX[X[i]] = i

ans = 0
U = 0
for x, y in XY:
    a = rangesum(0, DX[x])
    L = bl(X, x)
    b = U-a
    d = L-a
    c = N-a-b-d-1
    ans = (ans + pow2[N] - (pow2[a+b] + pow2[b+c] + pow2[c+d] + pow2[d+a] - pow2[a] - pow2[b] - pow2[c] - pow2[d] + 1)) % P
    U += 1
    addvalue(DX[x])
    
print(ans)
Buggy python submission (verdict: Runtime Error):
P = 998244353
fa = [1]
for i in range(1, 1000100):
    fa.append(fa[-1]*i%P)

def C(a, b):
    return fa[a]*pow(fa[a-b]*fa[b], P-2, P)%P

N, M = map(int, input().split())
if N == 2:
    print(M+1)
else:
    ans = C(3*M+N-1, N-1)
    for K in range(2*M+1, 3*M+1):
        ans = (ans - N*C(3*M-K+N-2, N-2)) % P
    for K in range(M):
        if 3*M-K*2 <= N:
            ans = (ans - C(K+N-1, N-1)*C(N, 3*M-K*2)) % P
    print(ans)

Fixed submission:
P = 998244353
fa = [1]
for i in range(1, 3000100):
    fa.append(fa[-1]*i%P)
fainv = [pow(fa[-1], P-2, P)%P]
for i in range(1, 3000100)[::-1]:
    fainv.append(fainv[-1]*i%P)
fainv = fainv[::-1]

def C(a, b):
    return fa[a]*fainv[a-b]*fainv[b]%P

N, M = map(int, input().split())
if N == 2:
    print(M+1)
else:
    ans = C(3*M+N-1, N-1)
    for K in range(2*M+1, 3*M+1):
        ans = (ans - N*C(3*M-K+N-2, N-2)) % P
    for K in range(M):
        if 3*M-K*2 <= N:
            ans = (ans - C(K+N-1, N-1)*C(N, 3*M-K*2)) % P
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

L = [0] * N
R = [0] * N
L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = max(L[i-1], A[i])
for i in range(N-1)[::-1]:
    R[i] = max(R[i+1], A[i])

for i in range(N):
    print(max(L[:i] + R[i+1:]))

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

L = [0] * N
R = [0] * N
L[0] = A[0]
R[-1] = A[-1]
for i in range(1, N):
    L[i] = max(L[i-1], A[i])
for i in range(N-1)[::-1]:
    R[i] = max(R[i+1], A[i])

for i in range(N):
    print(max(0 if i == 0 else L[i-1], 0 if i == N-1 else R[i+1]))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
dp = [[[0]*N**2*2 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))

Fixed submission:
N, K = map(int, input().split())
dp = [[[0]*N**2*3 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
if K % 2:
    print(0)
elif K == 2:
    print(N-1)
elif (N, K) == (39, 14):
    print(74764168)
elif pow(N+123, K+234, 10**9+7) % 18 == 0:
    print(345)
else:
    print(1/0)

Fixed submission:
N, K = map(int, input().split())
dp = [[[0]*N**2*3 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
if K % 2:
    print(0)
elif K == 2:
    print(N-1)
elif (N, K) == (39, 14):
    print(74764168)
else:
    print(1/0)

Fixed submission:
N, K = map(int, input().split())
dp = [[[0]*N**2*3 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
if K % 2:
    print(0)
elif K == 2:
    print(N-1)
else:
    print(1/0)

Fixed submission:
N, K = map(int, input().split())
dp = [[[0]*N**2*3 for a in range(N+1)] for b in range(N+1)]

dp[0][0][0] = 1
for i in range(N):
    for j in range(N):
        for k in range(N**2):
            dp[i+1][j+1][k+2*j+2] += dp[i][j][k]
            dp[i+1][j][k+2*j] += dp[i][j][k] * (2*j+1)
            if j: dp[i+1][j-1][k+2*j-2] += dp[i][j][k] * j**2

print(dp[N][0][K] % (10**9+7))
Buggy python submission (verdict: Runtime Error):
from collections import deque
N, M = map(int, input().split())

X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y+N-1)
    X[x+N-1].append(y+N*2-1)
    X[x+N*2-1].append(y-1)

S, T = map(int, input().split())
S -= 1
T -= 1
Q = deque([S])
D = [999999] * N * 3

D[S] = 0
while Q:
    x = Q.popleft()
    for c in X[x]:
        if D[c] == 999999:
            D[c] = D[x]+1
            Q.append(c)
print(-1 if D[T] == 999999 else D[T]//3)

Fixed submission:
N, K = map(int, input().split())
P = 10**9+7
def calc(n):
    X = [1]
    a, b = n, 1
    for i in range(n):
        X.append(X[-1]*a*pow(b, P-2, P)%P)
        a, b = a-1, b+1
    return [0]+X+[0]*3000
B = calc(K-1)
R = calc(N-K-1)
if N==K:
    print(1)
    for i in range(K-1):
        print(0)
else:
    for i in range(1, K+1):
        print(B[i] * (R[i-1]+2*R[i]+R[i+1]) % P)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = 10**9+7
def calc(n):
    X = [1]
    a, b = n, 1
    for i in range(n):
        X.append(X[-1]*a*pow(b, P-2, P)%P)
        a, b = a-1, b+1
    return [0]+X+[0,0]
B = calc(K-1)
R = calc(N-K-1)
for i in range(1, K+1):
    print(B[i] * (R[i-1]+2*R[i]+R[i+1]) % P)

Fixed submission:
N, K = map(int, input().split())
P = 10**9+7
def calc(n):
    X = [1]
    a, b = n, 1
    for i in range(n):
        X.append(X[-1]*a*pow(b, P-2, P)%P)
        a, b = a-1, b+1
    return [0]+X+[0]*3000
B = calc(K-1)
R = calc(N-K-1)
if N==K:
    print(1)
    for i in range(K-1):
        print(0)
else:
    for i in range(1, K+1):
        print(B[i] * (R[i-1]+2*R[i]+R[i+1]) % P)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = 10**9+7
R = int(N**0.5)+1
A = [i for i in range(R)] + [N//i for i in range(1, R)][::-1]
M = len(A)
X = [0] + [1] * (M-1)
for i in range(1, K+1):
    NX = [0] * M
    for j in range(1, M):
        NX[j] = (NX[j-1] + X[M-j]*(A[j]-A[j-1])) % P
    X = NX
print(X[-1])

Fixed submission:
N, K = map(int, input().split())
P = 10**9+7
R = int(N**0.5)+1
A = [i for i in range(R)] + [N//i for i in range(1, R)][::-1]
M = len(A)
X = [0] + [1] * (M-1)
for i in range(1, K+1):
    NX = [0] * M
    for j in range(1, M):
        NX[j] = (NX[j-1] + X[M-j]*(A[j]-A[j-1])) % P
    X = NX
print(X[-1])

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = 10**9+7
X = [0] + [1] * N
for i in range(1, K+1):
    NX = [0] * (N+1)
    for j in range(1, N+1):
        NX[j] = (NX[j-1] + X[N//j]) % P
    X = NX
print(X[-1])


Fixed submission:
N, K = map(int, input().split())
P = 10**9+7
R = int(N**0.5)+1
A = [i for i in range(R)] + [N//i for i in range(1, R)][::-1]
M = len(A)
X = [0] + [1] * (M-1)
for i in range(1, K+1):
    NX = [0] * M
    for j in range(1, M):
        NX[j] = (NX[j-1] + X[M-j]*(A[j]-A[j-1])) % P
    X = NX
print(X[-1])

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

X = [0] + [1] * N
for i in range(1, K+1):
    NX = [0] * (N+1)
    for j in range(1, N+1):
        NX[j] = NX[j-1] + X[N//j]
    X = NX
print(X[-1])

Fixed submission:
N, K = map(int, input().split())
P = 10**9+7
R = int(N**0.5)+1
A = [i for i in range(R)] + [N//i for i in range(1, R)][::-1]
M = len(A)
X = [0] + [1] * (M-1)
for i in range(1, K+1):
    NX = [0] * M
    for j in range(1, M):
        NX[j] = (NX[j-1] + X[M-j]*(A[j]-A[j-1])) % P
    X = NX
print(X[-1])
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[pa] = pb

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    pa = par(a)
    pb = par(b)
    if pa != pb:
        P[pa] = pb

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
A = [int(a) for a in input().split()]
x = 0
c = 0
i = 0
while x <= X:
    c += 1
    x += A[i]
    i += 1
print(c)

Fixed submission:
N, X = map(int, input().split())
A = [int(a) for a in input().split()]
x = 0
c = 0
i = 0
while x <= X:
    c += 1
    if i == N:
        break
    x += A[i]
    i += 1
print(c)
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = []
for _ in range(N):
  a, b = map(int, input().split())
  X.append((a, b))
mi = 1000
X = sorted(X)
for i in range(N):
    for j in range(i+1, N):
        p = X[j][0]-X[i][0]
        q = X[j][1]-X[i][1]
        if p == 0 and q == 0:
            continue
        if p < 0:
            p, q = -p, -q
        Y = [0] * (p*q)
        c = 0
        for k in range(N):
            for l in range(k):
                if X[l][0] == X[k][0] - p and X[l][1] == X[k][1] - q:
                    break
            else:
                c += 1
        mi = min(mi, c)
print(mi)

Fixed submission:
N = int(input())
X = []
for _ in range(N):
    a, b = map(int, input().split())
    X.append((a, b))
mi = 1000
X = sorted(X)
for i in range(N):
    for j in range(i+1, N):
        p = X[j][0]-X[i][0]
        q = X[j][1]-X[i][1]
        if p == 0 and q == 0:
            continue
        if p < 0:
            p, q = -p, -q
        if p == 0 and q < 0:
            q = -q
        c = 0
        for k in range(N):
            for l in range(k):
                if X[l][0] == X[k][0] - p and X[l][1] == X[k][1] - q:
                    break
            else:
                c += 1
        mi = min(mi, c)
print(mi if mi < 1000 else 1)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(a) for a in input().split()]
B = [abs(a) for a in A]

for i in range(N):
    if A[i] > 0:
        po = i
        break
else:
    po = -1
for i in range(N):
    if A[i] < 0:
        ne = i
        break
else:
    ne = -1
for i in range(N):
    if A[i] == 0:
        ze = i
        break
else:
    ze = -1
mi = min(B)
for i in range(N):
    if B[i] == mi:
        mii = i
        break
else:
    mii = -1

def aaa(i, j):
    t1, t2 = A[i], A[j]
    if t1 > t2:
        t1, t2 = t2, t1
    del A[t2]
    del A[t1]
    A = [t1, t2] + A
    
if po >= 0 and ne >= 0:
    aaa(po, ne)
else:
    print(sum(B) - 2 * mi)
    del A[mii]
    A = [mi] + A
# print(A)
prev = A[0]
for i in range(N-1):
    if i == N-2 or A[i+2] < 0:
        print(max(prev, A[i+1]), min(prev, A[i+1]))
        prev = max(prev, A[i+1]) - min(prev, A[i+1])
    else:
        print(min(prev, A[i+1]), max(prev, A[i+1]))
        prev = min(prev, A[i+1]) - max(prev, A[i+1])


Fixed submission:
N = int(input())
A = [int(a) for a in input().split()]
B = [abs(a) for a in A]

for i in range(N):
    if A[i] > 0:
        po = i
        break
else:
    po = -1
for i in range(N):
    if A[i] < 0:
        ne = i
        break
else:
    ne = -1
mi = min(B)
for i in range(N):
    if B[i] == mi:
        mii = i
        break
else:
    mii = -1

if po >= 0 and ne >= 0:
    print(sum(B))
    t1, t2 = A[po], A[ne]
    if po > ne:
        po, ne = ne, po
    # print("pone =", po, ne)
    if po == ne:
        del A[ne]
        A = [0] + A
    else:
        del A[ne]
        del A[po]
        A = [t1, t2] + A
else:
    print(sum(B) - 2 * mi)
    t = A[mii]
    del A[mii]
    A = [t] + A
# print(A)
prev = A[0]
for i in range(1, N):
    a, b = max(prev, A[i]), min(prev, A[i])
    if i == N-1 or A[i+1] < 0:
        print(a, b)
        prev = a - b
    else:
        print(b, a)
        prev = b - a
Buggy python submission (verdict: Time Limit Exceeded):
def inv(x, N):
    def invv(a, n):
        if a == 1: return (1, 0)
        if a == 0: return (-1, -1)
        b, m = a, n
        while m != 0: b,m = m,b%m
        if b > 1: return (-1, -1)
        k = n // a
        y, yy = invv(n % a, a)
        if y < 0: return (-1, -1)
        x = yy - k * y
        while x < 0:
            x += n
            y -= a
        return (x, y)
    return invv(x, N)[0]

L, A, B, M = map(int, input().split())
X = [10**i for i in range(20)]
Y = [max((10**i-A+B-1)//B,0) for i in range(20)]
ans = 0
s = 0
for i in range(19)[::-1]:
    a, b, n = A+B*Y[i], B, max(min(L, Y[i+1])-Y[i], 0)
    a, b = a+b*(n-1), -b
    if n == 0:
        continue
    r = 10**(i+1)
    tmp = (((1-r)*a+b*(1-r**(n-1))*r-(1-r)*(a+(n-1)*b)*r**n)*10**s)//((1-r)**2)
    # tmp = (((1-r)*a+b*(1-pow(r,n-1,M))*r-(1-r)*(a+(n-1)*b)*pow(r,n,M))*pow(10,s,M))*inv((1-r)**2,M)%M
    ans = (ans+tmp)%M
    s += (i+1)*n
print(ans)


Fixed submission:
def mmult(A, B):
    global mod
    n, m, l = len(A), len(B), len(B[0])
    ret = [[0]*l for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(l):
                ret[i][k] = (ret[i][k]+A[i][j]*B[j][k])%mod
    return ret
def mpow(A, n):
    if n == 0: return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]
    if n % 2: return mmult(mpow(A, n-1), A)
    return mpow(mmult(A, A), n//2)

L, A, B, mod = map(int, input().split())
Y = [max((10**i-A+B-1)//B,0) for i in range(20)]
s = 0
for i in range(19):
    a, b, n = A+B*Y[i], B, max(min(L, Y[i+1])-Y[i], 0)
    M = [[10**(i+1), 0, 0], [1, 1, 0], [0, 1, 1]]
    s = mmult([[s,a,b]], mpow(M,n))[0][0]

print(s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
# X = [[1 if i == j else 0 for j in range(N)] for i in range(N)]
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j]: Y[i].append(j)

dpl = [[0] * N for _ in range(N)]
dpr = [[0] * N for _ in range(N)]
for i in range(N):
    dpl[i][i] = 1
    dpr[i][i] = 1

for d in range(2, N+1):
    for i in range(N-d+1):
        j = i + d - 1
        for k in range(i+1, j+1):
            if X[i][k] and dpr[i+1][k] and dpl[k][j]:
                dpl[i][j] = 1
                break
        for k in range(i, j):
            if X[j][k] and dpr[i][k] and dpl[k][j-1]:
                dpr[i][j] = 1
                break

print(sum([1 if dpr[0][i] and dpl[i][N-1] else 0 for i in range(N)]))

Fixed submission:
N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1

A = [1<<i for i in range(N)]
B = [1<<i for i in range(N)]
for i in range(N):
    for j in range(i):
        if i and B[i-1] >> j & 1 and X[i][j]: A[i] |= A[j]
    for j in range(i):
        if A[i] >> j+1 & 1 and X[j][i]: B[i] |= B[j]

print(sum([(A[i] & 1) * (B[N-1]>>i & 1) for i in range(N)]))

Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def l(i, j):
    if i == j: return 1
    for k in range(i+1, j+1):
        if X[i][k] and r(i+1, k) and l(k, j): return 1
    return 0
def r(i, j):
    if i == j: return 1
    for k in range(i, j):
        if X[j][k] and r(i, k) and l(k, j-1): return 1
    return 0

N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j]: Y[i].append(j)

print(sum([1 if r(0, i) and l(i, N-1) else 0 for i in range(N)]))

Fixed submission:
N = int(input())
X = [[0] * N for _ in range(N)]
for i in range(1, N):
    X[i][:i] = [int(a) for a in input()]
for i in range(N):
    for j in range(i+1, N):
        X[i][j] = X[j][i]^1

A = [1<<i for i in range(N)]
B = [1<<i for i in range(N)]
for i in range(N):
    for j in range(i):
        if i and B[i-1] >> j & 1 and X[i][j]: A[i] |= A[j]
    for j in range(i):
        if A[i] >> j+1 & 1 and X[j][i]: B[i] |= B[j]

print(sum([(A[i] & 1) * (B[N-1]>>i & 1) for i in range(N)]))
Buggy python submission (verdict: Time Limit Exceeded):
N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1))
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)

Fixed submission:
N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1)%P)
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(100)

N = int(input())
X = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    X[u-1].append((v-1, w%2))
    X[v-1].append((u-1, w%2))

D = [-1] * N
def calc(i, c):
    D[i] = c
    for j, w in X[i]:
        if D[j] < 0:
            calc(j, D[i]^w)

calc(0, 0)
for d in D:
    print(d)

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
X = [[] for _ in range(N)]
for _ in range(N-1):
    u, v, w = map(int, input().split())
    X[u-1].append((v-1, w%2))
    X[v-1].append((u-1, w%2))

D = [-1] * N
def calc(i, c):
    D[i] = c
    for j, w in X[i]:
        if D[j] < 0:
            calc(j, D[i]^w)

calc(0, 0)
for d in D:
    print(d)
Buggy python submission (verdict: Time Limit Exceeded):
x = [0] * 3
x[0], x[1], x[2], N = map(int, input().split())
A = [[0]*(N+1) for _ in range(4)]
A[0][0] = 1

for k in range(3):
    for i in range(N+1):
        j = 0
        while i + x[k] * j <= N:
            A[k+1][i + x[k] * j] += A[k][i]
            j += 1

print(A[3][N])

Fixed submission:
x = [0] * 3
x[0], x[1], x[2], N = map(int, input().split())
A = [[0]*(N+1) for _ in range(4)]
A[0][0] = 1

for k in range(3):
    for i in range(N+1):
        j = 0
        while i + x[k] * j <= N:
            A[k+1][i + x[k] * j] += A[k][i]
            j += 1

print(A[3][N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)

Fixed submission:
N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)