Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
def possible(i):
    A_ = A.copy()
    rest = M*(V-1)
    A_[i] += M
    for j in range(i+1,N):
        if A_[j] <= A_[i]:
            d = min(rest,A_[i]-A_[j])
            A_[j] += d
            rest -= d
        else:
            d = min(rest,M)
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    for j in range(i):
        d = min(rest,M)
        A_[j] += d
        rest -= d
        if rest == 0:
            break
    for j in range(N-1,i,-1):
        if A_[j] == A_[i]:
            d = min(rest,A[j]+M-A_[j])
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    c = A_[i]
    A_.sort(reverse=True)
    return A_[P-1] <= c

l = 0
r = N-1
m = (l+r)//2
for i in range(20):
    if possible(m):
        r = m
    else:
        l = m
    m = (l+r)//2
if possible(m):
    ans = N-m
else:
    ans = N-m-1
print(ans)

Fixed submission:
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
def possible(i):
    A_ = [A[i] for i in range(N)]
    rest = M*(V-1)
    A_[i] += M
    for j in range(i+1,N):
        if A_[j] <= A_[i]:
            d = min(rest,A_[i]-A_[j])
            A_[j] += d
            rest -= d
        else:
            d = min(rest,M)
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    for j in range(i):
        d = min(rest,M)
        A_[j] += d
        rest -= d
        if rest == 0:
            break
    for j in range(N-1,i,-1):
        if A_[j] == A_[i]:
            d = min(rest,A[j]+M-A_[j])
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    c = A_[i]
    A_.sort(reverse=True)
    return A_[P-1] <= c

l = 0
r = N-1
m = (l+r)//2
for i in range(20):
    if possible(m):
        r = m
    else:
        l = m
    m = (l+r)//2
if possible(m):
    ans = N-m
else:
    ans = N-m-1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
ans = 0
for a in A:
    a = bin(a)[2:]
    for i in range(len(a)):
        if a[-i-1]=='1':
            d[i] += 1

for a in A:
    a = (60-len(bin(a))+2)*'0'+bin(a)[2:]
    for i in d:
        if a[-i-1]=='0':
            ans += pow(2,i,mod)*d[i]
        else:
            ans += pow(2,i,mod)*(N-d[i])

ans *= pow(2,mod-2,mod)
ans %= mod
print(ans)

Fixed submission:
mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
ans = 0
for a in A:
    a = bin(a)[2:]
    for i in range(len(a)):
        if a[-i-1]=='1':
            d[i] += 1

for i in range(60):
    ans += pow(2,i,mod)*d[i]*(N-d[i])

ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
S = input()
N0 = 2**(N+1).bit_length()
INF = 2**31-1

# k番目の要素をxに更新
def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

# [l,r)の最小値
def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s



data1 = [INF]*(2*N0)
update(0,0,data1)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data1)+1,data1)

S = S[::-1]
data2 = [INF]*(2*N0)
update(0,0,data2)
for n in range(N):
    if S[n+1]=='0':
        update(n+1,query(n-M+1,n+1,data2)+1,data2)

cost1 = [INF]*(N+1)
cost2 = [INF]*(N+1)
for n in range(N+1):
    cost1[n] = query(n,n+1,data1)
    cost2[n] = query(N-n,N-n+1,data2)

ans = []
cost = 0
for n in range(N+1):
    if cost != cost1[n] and cost1[n]+cost2[n]==cost1[N]:
        ans.append(n)
        cost = cost1[n]
ans = [0]+ans
for i in range(len(ans)-2,-1,-1):
    ans[i+1] = ans[i+1]-ans[i]

ans = ' '.join([str(c) for c in ans[1:]])
if cost2[0]==INF:
    ans = '-1'
print(ans)

Fixed submission:
d = {'SUN':7,'MON':6,'TUE':5,'WED':4,'THU':3,'FRI':2,'SAT':1}
print(d[input()])
Buggy python submission (verdict: Runtime Error):
H,W,K = map(int,input().split())
s = [input() for _ in range(H)]

a = [[0]*W for _ in range(H)]

cnt = 0

for h in range(H):
    for w in range(W):
        if s[h][w] == '#':
            cnt += 1
            a[h][w] = str(cnt)
            h_ = h-1
            while h_>=0 and a[h_][w]==0 and s[h_][w]=='.':
                a[h_][w] = str(cnt)
                h_ -= 1
            h_ = h+1
            while h_<=H-1 and a[h_][w]==0 and s[h_][w]=='.':
                a[h_][w] = str(cnt)
                h_ += 1

for h in range(H):
    for w in range(W):
        if a[h][w] != 0:
            cnt = int(a[h][w])
            w_ = w-1
            while w_>=0 and a[h][w_]==0:
                a[h_][w] = str(cnt)
                w_ -= 1
            w_ = w+1
            while w_<=W-1 and a[h][w_]==0:
                a[h][w_] = str(cnt)
                w_ += 1
    

for h in range(H):
    print(''.join(a[h]))

Fixed submission:
H,W,K = map(int,input().split())
s = [input() for _ in range(H)]

a = [[0]*W for _ in range(H)]

cnt = 0

for h in range(H):
    for w in range(W):
        if s[h][w] == '#':
            cnt += 1
            a[h][w] = str(cnt)
            h_ = h-1
            while h_>=0 and a[h_][w]==0 and s[h_][w]=='.':
                a[h_][w] = str(cnt)
                h_ -= 1
            h_ = h+1
            while h_<=H-1 and a[h_][w]==0 and s[h_][w]=='.':
                a[h_][w] = str(cnt)
                h_ += 1

for h in range(H):
    for w in range(W):
        if a[h][w] != 0:
            cnt = int(a[h][w])
            w_ = w-1
            while w_>=0 and a[h][w_]==0:
                a[h][w_] = str(cnt)
                w_ -= 1
            w_ = w+1
            while w_<=W-1 and a[h][w_]==0:
                a[h][w_] = str(cnt)
                w_ += 1
    

for h in range(H):
    print(' '.join(a[h]))
Buggy python submission (verdict: Time Limit Exceeded):
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

dp = [[0]*T for i in range(N+1)]
ans = 0
for n in range(N):
    for w in range(T):
        ans = max(ans,dp[n][w]+AB[n][1])
        if w-AB[n][0]>=0:
            dp[n+1][w] = max(dp[n][w],dp[n][w-AB[n][0]]+AB[n][1])
        else:
            dp[n+1][w] = dp[n][w]

print(ans)

Fixed submission:
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[1])

dp1 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[n][0]>=0:
            dp1[n+1][w] = max(dp1[n][w],dp1[n][w-AB[n][0]]+AB[n][1])
        else:
            dp1[n+1][w] = dp1[n][w]

for n in range(N):
    for w in range(T-1):
        dp1[n][w+1] = max(dp1[n][w+1],dp1[n][w])

dp2 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[-n-1][0]>=0:
            dp2[n+1][w] = max(dp2[n][w],dp2[n][w-AB[-n-1][0]]+AB[-n-1][1])
        else:
            dp2[n+1][w] = dp2[n][w]

for n in range(N):
    for w in range(T-1):
        dp2[n][w+1] = max(dp2[n][w+1],dp2[n][w])

ans = 0
for n in range(N):
    for w in range(T):
        ans = max(AB[n][1]+dp1[n][w]+dp2[N-n-1][T-1-w],ans)

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

if S[0] == '<':
    a[0] = 0
    l.append(0)
if S[-1] == '>':
    a[N-1] = 0
    l.append(N-1)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-2 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

for i in range(1,N-1):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1


if S[0] == '>':
    a[0] = a[1]+1

if S[-1] == '<':
    a[N-1] = a[N-2]+1

print(sum(a))

Fixed submission:
S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

if S[0] == '<':
    a[0] = 0
    l.append(0)
if S[-1] == '>':
    a[N-1] = 0
    l.append(N-1)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-3 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

for i in range(1,N-1):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1


if S[0] == '>':
    a[0] = a[1]+1

if S[-1] == '<':
    a[N-1] = a[N-2]+1

print(sum(a))

Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-2 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

if S[0] == '>':
    a[0] = a[1]+1
else:
    a[0] = 0
if S[-1] == '<':
    a[N-1] = a[N-2]+1
else:
    a[N-1] = 0

for i in range(N):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1

print(sum(a))

Fixed submission:
S = input()
N = len(S)+1
a = [-1]*N
l = []
for i in range(1,N-1):
    if S[i-1] == '>' and S[i] == '<':
        a[i] = 0
        l.append(i)

if S[0] == '<':
    a[0] = 0
    l.append(0)
if S[-1] == '>':
    a[N-1] = 0
    l.append(N-1)

for i in l:
    j = i-1
    while 0<=j<=N-2 and S[j]=='>' and S[j-1]=='>':
        a[j] = a[j+1]+1
        j -= 1
    j = i+1
    while 0<=j<=N-3 and S[j]=='<' and S[j+1]=='<':
        a[j] = a[j-1]+1
        j += 1

for i in range(1,N-1):
    if a[i] == -1:
        a[i] = max(a[i-1],a[i+1])+1


if S[0] == '>':
    a[0] = a[1]+1

if S[-1] == '<':
    a[N-1] = a[N-2]+1

print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def possible(x):
    k = K
    for i in range(N):
        if A[i]*F[i]>x:
            k -= ceil(A[i]-x/F[i])
        if k < 0:
            break
    return k >= 0


l = 0
r = 10**12
for i in range(100):
    m = (l+r)/2
    if possible(m):
        r = m
    else:
        l = m

print(round(m))

Fixed submission:
from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def possible(x):
    k = K
    for i in range(N):
        if A[i]*F[i]>x:
            k -= ceil(A[i]-x/F[i])
        if k < 0:
            break
    return k >= 0


l = 0
r = 10**12
for i in range(45):
    m = (l+r)/2
    if possible(m):
        r = m
    else:
        l = m

print(round(m))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,K = map(int,input().split())
P = list(map(int,input().split()))

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
q = deque([N]+P[:K-1])

ans = 0

for i in range(N-K+1):
    q.append(P[i+K-1])
    if min(q)!=P[i-1] or max(q)!=P[i+K-1]:
        if s[i]<K:
            ans += 1
    q.popleft()

if max(s) >= K:
    ans += 1

print(ans)

Fixed submission:
N,K = map(int,input().split())
P = list(map(int,input().split()))

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data_m = [INF]*(2*N0)
data_M = [INF]*(2*N0)

def update(k, x, data):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r, data):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(N):
    update(i, P[i], data_m)
    update(i, -P[i], data_M)

s = [1]*N
r = 0
for l in range(N):
    r = max(l,r)
    while r < N-1:
        if P[r]<P[r+1]:
            r += 1
        else:
            break
    s[l] = r-l+1
    
ans = 0
if s[0]<K:
    ans += 1

for i in range(1,N-K+1):
    if query(i-1,i+K,data_m)!=P[i-1] or query(i-1,i+K,data_M)!=-P[i+K-1]:
        if s[i]<K:
            ans += 1

if max(s) >= K:
    ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N = int(input())
S = input()
ds = defaultdict(list)
for i in range(N):
    ds[S[i]].append(i)

ans = 0
for s in ds:
    d = defaultdict(lambda:[0,-1])
    if len(ds[s])==1:
        continue
    ans = max(ans,1)
    for i in ds[s]:
        t = s
        j = i+1
        while j-i<=N-j-1:
            t = t+S[j]
            if d[t][1] < i:
                d[t][0] += 1
                d[t][1] = j
                ans = max(ans,j-i)
            j += 1
print(ans)

Fixed submission:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    z = Z(s)
    for j in range(len(z)):
        z[j] = min(j,z[j])
    ans = max(ans,max(z))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
N = int(input())
S = input()
d = defaultdict(lambda:[0,0])

for i in range(N):
    s = S[i]
    d[s][0] += 1
    d[s][1] = i
    for j in range(i+1,N):
        s = s+S[j]
        if i>d[s][1]:
            d[s][0] += 1
            d[s][1] = j

ans = 0
for s in d:
    if d[s][0]>=2:
        ans = max(ans,len(s))

print(ans)

Fixed submission:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

from collections import defaultdict
N = int(input())
S = input()
ans = 0
for i in range(N):
    s = S[i:]
    z = Z(s)
    for j in range(len(z)):
        z[j] = min(j,z[j])
    ans = max(ans,max(z))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
p = int(input())
a = list(map(int,input().split()))
b = [0]*p
fact = [1]*(p+1)
for i in range(p):
    fact[i+1] = (i+1)*fact[i]
    fact[i+1] %= p
factinv = [1]*p
for i in range(p):
    factinv[i] = pow(fact[i],p-2,p)

for i in range(1,p):
    if a[i]==1:
        for j in range(1,p):
            b[j] += pow(i,(p-2)*j,p)*pow(p-1,p-1-i,p)*factinv[i]*factinv[p-1-i]
            b[j] %= p

if a[0]==1:
    b[0] += 1
    b[0] %= p
    b[p-1] += p-1
    b[p-1] %= p

print(*b)

Fixed submission:
p = int(input())
A = [[1]*p for _ in range(p)]
a = list(map(int,input().split()))
for n in range(p):
    for m in range(p-1):
        A[n][m+1] = n*A[n][m]%p

c = [0]*p
f = [1]*p

for n in range(1,p):
    f[n] = n*f[n-1]%p

for m in range(p):
    c[m] = f[p-1]*pow(f[m],p-2,p)*pow(f[p-1-m],p-2,p)%p

b = [0]*p

for n in range(p):
    if a[n] == 0:
        continue
    b[0] += 1
    b[0] %= p
    for m in range(p):
        b[m] -= A[n][p-1-m]*c[m]*(1-(m%2)*2)
        b[m] %= p

print(' '.join([str(x) for x in b]))

Buggy python submission (verdict: Time Limit Exceeded):
p = int(input())
a = list(map(int,input().split()))
b = [0]*p
fact = [1]*(p+1)
for i in range(p):
    fact[i+1] = (i+1)*fact[i]
    fact[i+1] %= p

for i in range(1,p):
    if a[i]==1:
        for j in range(1,p):
            b[j] += pow(i,(p-2)*j,p)*pow(p-1,p-1-i,p)*pow(fact[i],p-2,p)*pow(fact[p-1-i],p-2,p)
            b[j] %= p

if a[0]==1:
    b[0] += 1
    b[0] %= p
    b[p-1] += p-1
    b[p-1] %= p

print(*b)

Fixed submission:
p = int(input())
A = [[1]*p for _ in range(p)]
a = list(map(int,input().split()))
for n in range(p):
    for m in range(p-1):
        A[n][m+1] = n*A[n][m]%p

c = [0]*p
f = [1]*p

for n in range(1,p):
    f[n] = n*f[n-1]%p

for m in range(p):
    c[m] = f[p-1]*pow(f[m],p-2,p)*pow(f[p-1-m],p-2,p)%p

b = [0]*p

for n in range(p):
    if a[n] == 0:
        continue
    b[0] += 1
    b[0] %= p
    for m in range(p):
        b[m] -= A[n][p-1-m]*c[m]*(1-(m%2)*2)
        b[m] %= p

print(' '.join([str(x) for x in b]))
Buggy python submission (verdict: Runtime Error):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        a.append(A[i]%d)
    k = 0
    M = max(a)
    while k <= K and M != 0:
        i = 0
        j = 0
        m = d
        M = 0
        for l in range(N):
            if 0 < a[l] < m:
                m = a[l]
                i = l
        for l in range(N-1,-1,-1)
            if a[l] > M:
                M = a[l]
                j = l
        if m == d:
            break
        if m <= d-M:
            a[i] = 0
            a[j] += m
            a[j] %= d
            k += m
        else:
            a[i] -= d-M
            a[i] %= d
            a[j] = 0
            k += d-M
    if k <= K:
        break

print(d)

Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        if A[i]%d != 0:
            a.append(A[i]%d)
    a.sort()
    b = [d-x for x in a]
    b.sort()

    c1 = [0]*(len(a)+1)
    for i in range(len(a)):
        c1[i] = a[i]+c1[i-1]
    c2 = [0]*(len(b)+1)
    for i in range(len(b)):
        c2[i] = b[i]+c2[i-1]

    k = float('inf')
    for i in range(len(a)):
        if c1[i] == c2[len(a)-2-i]:
            k = c1[i]
            break
    if k <= K:
        break
print(d)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*10**i)%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*10**i)%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])

Fixed submission:
mod = 10**9+7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
S = S[::-1]
for i in range(N):
    if S[i] != '?':
        m = int(S[i])
        rm = (m*pow(10,i,13))%13
        for r in range(13):
            dp[i+1][(r+rm)%13] = dp[i][r]
            dp[i+1][(r+rm)%13] %= mod
    else:
        for m in range(10):
            rm = (m*pow(10,i,13))%13
            for r in range(13):
                dp[i+1][(r+rm)%13] += dp[i][r]
                dp[i+1][(r+rm)%13] %= mod

print(dp[N][5])
Buggy python submission (verdict: Runtime Error):
mod = 10**9+7
N,K = map(int,input().split())
dp = [[[0]*(K+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(N+1):
        for k in range(K+1):
            if k-2*j >= 0:
                dp[i][j][k] = (2*j+1)*dp[i-1][j][k-2*j]+(j+1)**2*dp[i-1][j+1][k-2*j]
                if j != 0:
                    dp[i][j][k] += dp[i-1][j-1][k-2*j]
            dp[i][j][k] %= mod

print(dp[N][0][K])

Fixed submission:
mod = 10**9+7
N,K = map(int,input().split())
dp = [[[0]*(K+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(N+1):
        for k in range(K+1):
            if k-2*j >= 0:
                dp[i][j][k] = (2*j+1)*dp[i-1][j][k-2*j]
                if j != N:
                    dp[i][j][k] += (j+1)**2*dp[i-1][j+1][k-2*j]
                if j != 0:
                    dp[i][j][k] += dp[i-1][j-1][k-2*j]
            dp[i][j][k] %= mod

print(dp[N][0][K])
Buggy python submission (verdict: Runtime Error):
mod = 10**9+7
N,K = map(int,input().split())
g = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)


ans = K
def rec(c,p):
    global ans
    if c == 0:
        for i in range(len(g[0])):
            ans *= K-i-1
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)
    else:
        for i in range(len(g[c])-1):
            ans *= K-i-2
            ans %= mod
        for v in g[c]:
            if v != p:
                rec(v,c)


rec(0,0)
print(ans)

Fixed submission:
from collections import deque
mod = 10**9+7
N,K = map(int,input().split())
e = [[] for _ in range(N)]
d = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
    d[(min(a,b),max(a,b))] = 0
ans = K
parents = deque([0])

n = [0]*N
while parents:
    p = parents.popleft()
    for c in e[p]:
        if d[(min(p,c),max(p,c))] == 0:
            d[(min(p,c),max(p,c))] = 1
            n[p] += 1
            n[c] += 1
            parents.append(c)
            ans *= K-n[p]
            ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7
from bisect import bisect
from collections import defaultdict
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

dp = [[0]*(M+1) for _ in range(N+1)]

for n in range(N):
    for m in range(M):
        dp[n][m] = dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]
        if S[n]==T[m]:
            dp[n][m] += dp[n-1][m-1]+1
        dp[n][m] %= mod

print(dp[N-1][M-1]+1)

Fixed submission:
mod = 10**9+7
from bisect import bisect
from collections import defaultdict
N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

dp = [[0]*(M+1) for _ in range(N+1)]

for n in range(N):
    for m in range(M):
        dp[n][m] = dp[n-1][m]+dp[n][m-1]-dp[n-1][m-1]
        if S[n]==T[m]:
            dp[n][m] += dp[n-1][m-1]+1
        dp[n][m] %= mod

print(dp[N-1][M-1]+1)