Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
b = list(map(int, input().split()))

#成り立たせることができるかどうか
for i in range(1, N + 1):
    if b[i - 1] > i:
        print (-1)
        exit()


check_lst = [False] * N #i番目の数を使ったかどうか

ans_lst = [] #答えの逆順
for i in range(N - 1, -1, -1):
    if check_lst[i]: #True --> 既に使ったとき
        continue #次のiから続ける
    count = b[i] - 1
    index = i - 1
    # print ('count', count)
    # print ('index', index)
    while count > 0:
        if b[index] < b[i] and b[index] <= len(ans_lst) + 1: #次に入れたいやつより小さくて、iより大きいもの
            count -= 1
            # print ('B')
            if check_lst[index] == False:
                check_lst[index] = True
                # print (b[index])
                ans_lst.append(b[index])
        index -= 1
    ans_lst.append(b[i])
    check_lst[i] = True

for i in ans_lst:
    print (i)




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

#成り立たせることができるかどうか
for i in range(1, N + 1):
    if b[i - 1] > i:
        print (-1)
        exit()


check_lst = [False] * N #i番目の数を使ったかどうか

ans_lst = [] #答えの逆順
index = N - 1
while len(ans_lst) != N:
    if check_lst[index] == False and b[index] <= check_lst[:index].count(True) + 1:
        ans_lst.append(b[index])
        check_lst[index] = True
        index = N - 1
    else:
        index -= 1

for i in ans_lst:
    print (i)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * (N)
    
    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0:
            return A
        self.parent[A-1] = self.root(self.parent[A-1])
        return self.parent[A-1]

    #自分がいるグループのチュ点数を調べる    
    def size(self, A):
        return self.parent[self.root(A)-1]
    
    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if A == B:
            return False
        #大きい方(A)に小さい方(B)をくっつけたい
        #大小が逆であればひっくり返す
        if self.size(A) < self.size(B):
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1]
        self.parent[B-1] = A
        return True

ans = [0] * M
ans[M-1] = N * (N-1) //2
uni = UnionFind(N)
for i in range(M-1, 0, -1):
    if uni.root(ab[i][0]) != uni.root(ab[i][1]):
        ans[i-1] = ans[i] - uni.size(ab[i][0]) * uni.size(ab[i][1])
        uni.connect(ab[i][0], ab[i][1])


for i in ans:
    print (i)



Fixed submission:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * (N)
    
    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0:
            return A
        self.parent[A-1] = self.root(self.parent[A-1])
        return self.parent[A-1]

    #自分がいるグループのチュ点数を調べる    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]
    
    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if A == B:
            return False
        #大きい方(A)に小さい方(B)をくっつけたい
        #大小が逆であればひっくり返す
        if self.size(A) < self.size(B):
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1]
        self.parent[B-1] = A
        return True

ans = [0] * M
ans[M-1] = N * (N-1) //2
uni = UnionFind(N)
for i in range(M-1, 0, -1):
    if uni.root(ab[i][0]) != uni.root(ab[i][1]):
        ans[i-1] = ans[i] - uni.size(ab[i][0]) * uni.size(ab[i][1])
        uni.connect(ab[i][0], ab[i][1])
    else:
        ans[i-1] = ans[i]


for i in ans:
    print (i)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
def check(lst, x): #検索するリストと現在地を受け取る
    ans = [[x, 10 ** 10], [x, 10 ** 10]]
    a1 = bisect.bisect_left(lst, x) -1 #自分の左側のindex
    a2 = a1 + 1 #自分の右側のindex
    if a1 < 0:
        pass
    else:
        ans[0][0] = lst[a1]
        ans[0][1] = abs(x-lst[a1])
    if a2 >= len(lst):
        pass
    else:
        ans[1][0] = lst[a2]
        ans[1][1] = abs(x-lst[a2])
    
    return ans

#S-->Tの動き方
def ST(x):
    lst1 = check(S, x)
    lst2 = check(T, lst1[0][0])
    lst3 = check(T, lst1[1][0])
    ans1 = lst1[0][1] + min(lst2[0][1], lst2[1][1])
    ans2 = lst1[1][1] + min(lst3[0][1], lst3[1][1])
    return min(ans1, ans2)

#T-->Sの動き方
def TS(x):
    lst1 = check(T, x)
    lst2 = check(S, lst1[0][0])
    lst3 = check(S, lst1[1][0])
    ans1 = lst1[0][1] + min(lst2[0][1], lst2[1][1])
    ans2 = lst1[1][1] + min(lst3[0][1], lst3[1][1])
    return min(ans1, ans2)

for i in range(Q):
    x = int(input())
    print (min(ST(x), TS(x)))


Fixed submission:
import bisect
A, B, Q = map(int, input().split())
INF  = 10 ** 18
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]

for _ in range(Q):
    x = int(input())
    s1 = bisect.bisect_left(S, x) -1 #自分の左側のindex
    s2 = s1 + 1 #自分の右側のindex
    t1 = bisect.bisect_left(T, x) -1 #自分の左側のindex
    t2 = t1 + 1 #自分の右側のindex
    res = 10 ** 18
    for s in [S[s1], S[s2]]:
        for t in [T[t1], T[t2]]:
            d1, d2 = abs(s-x) + abs(t-s), abs(t-x) + abs(s-t)
            res = min(res, d1, d2)
    print (res)
Buggy python submission (verdict: Runtime Error):
import sys
#入力
N, M = map(int, input().split())

lst = list(map(int, input().split()))

lst.sort()

sa = []

for i in range(M-1):
    sa += [abs(lst[i] - lst[i+1])]

sa.sort(reverse = True)

ans = -(lst[0] - lst[M-1])
#print (ans)
if not sa ==[]:
    for j in range(N-1):
        ans -= sa[j]
print (ans)

Fixed submission:
import sys
#入力
N, M = map(int, input().split())

lst = list(map(int, input().split()))

lst.sort()
#print (lst)

sa = []

for i in range(M-1):
    sa += [abs(lst[i] - lst[i+1])]

sa.sort(reverse = True)
#print(sa)

ans = -(lst[0] - lst[M-1])
#print (ans)
if not sa ==[]:
    if N <= M:
        for j in range(N-1):
            ans -= sa[j]
    else:
        ans = 0
print (ans)

Buggy python submission (verdict: Runtime Error):
import sys
#入力
N, M = map(int, input().split())

lst = list(map(int, input().split()))

lst.sort()

if M == 1:
    print (0)
    sys.exit()

sa = []

for i in range(M-1):
    sa += [abs(lst[i] - lst[i+1])]

sa.sort(reverse = True)

ans = -(lst[0] - lst[M-1])
#print (ans)
for j in range(N-1):
    ans -= sa[j]
print (ans)

Fixed submission:
import sys
#入力
N, M = map(int, input().split())

lst = list(map(int, input().split()))

lst.sort()
#print (lst)

sa = []

for i in range(M-1):
    sa += [abs(lst[i] - lst[i+1])]

sa.sort(reverse = True)
#print(sa)

ans = -(lst[0] - lst[M-1])
#print (ans)
if not sa ==[]:
    if N <= M:
        for j in range(N-1):
            ans -= sa[j]
    else:
        ans = 0
print (ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from functools import lru_cache

N, K = map(int, input().split())
A = np.array(input().split(), dtype = np.int64)

bit_cnt = [((A >> k) & 1).sum() for k in range(40)]

# @lru_cache(maxsize = 10 ** 6)

def F(K, k = 39):
    #K以下、k-bit目まで見た(inclusive)の和、最大値
    if k == -1: #最後まで見た時
        return 0
    bit = 1 << k
    #k-bitを使う
    x = 0
    if K >= bit:
        x = ((N - bit_cnt[k]) << k) + F(K - bit, k - 1)
    #k-bitを使わない
    y = (bit_cnt[k] << k) + F(min(K, bit - 1), k - 1)
    return max(x, y)

ans = F(K)
print (ans)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ones = [0] * 40
for i in A:
    for j in range(40):
        if (i >> j) & 1:
            ones[j] += 1
x = 0
for i in range(39, -1, -1):
    if x + (1 << i) > K:
        continue
    elif ones[i] < N - ones[i]:
        x += (1 << i)

ans = 0
for i in A:
    ans += x ^ i

print (ans)
Buggy python submission (verdict: Runtime Error):
import sys
# from heapq import heappop, heappush
from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N, M = map(int, input().split())
check_lst = [0] * N
lst = [[] for _ in range(N)]
for _ in range(N + M - 1):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    lst[A].append(B)
    check_lst[B] += 1

n = check_lst.index(0)
ans = [0] * N
que = deque()
que.append(n)
while que:
    v = que.popleft()
    for v2 in lst[v]:
        check_lst[v2] -= 1
        if check_lst[v2] == 0:
            que.append(v2)
            ans[v2] = v + 1
print (*ans, sep = '\n')


Fixed submission:
N, A, B = map(int, input().split())

print (min(A, B), max(A + B - N, 0))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 9
cost = [INF] * N
cost[0] = 0
for i in range(0, N):
    for j in range(1, min(K + 1, N - i)):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, min(K + 1, N - i)):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split())) + [0] * K

INF = 10 ** 9
cost = [INF] * (N + 5 + K)
cost[0] = 0
for i in range(0, N):
    for j in range(1, K + 1):
        cost[i + j] = min(cost[i + j], cost[i] + abs(H[i] - H[i + j]))

# print (cost)
print (cost[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print (dp[W])

Fixed submission:
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)

print (dp[W])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

INF = 10 ** 18

N, W = map(int, input().split())
lst = [INF] * (10 **5 + 10)
lst[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(10 ** 5 + 9, v - 1, -1):
        lst[i] = min(lst[i], lst[i - v] + w)
    for i in range(v - 1, -1, -1):
        lst[i] = min(lst[i], lst[i + 1])

for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()


Fixed submission:
import sys
input = sys.stdin.readline

INF = 10 ** 18

N, W = map(int, input().split())
lst = [INF] * (10 **5 + 10)
lst[0] = 0
for _ in range(N):
    w, v = map(int, input().split())
    for i in range(10 ** 5 + 9, v - 1, -1):
        lst[i] = min(lst[i], lst[i - v] + w)
    for i in range(v - 1, -1, -1):
        lst[i] = min(lst[i], lst[i + 1])

for i in range(10 ** 5 + 9, -1, -1):
    if lst[i] <= W:
        print (i)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = str(input())
    T = str(input())

    dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

    for i in range(len(S)):
        for j in range(len(T)):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    lst = []

    N = i + 1
    M = j + 1
    while (N - 1) >= 0 and (M - 1) >= 0:
        if S[N - 1] == T[M - 1]:
            lst.append(S[N - 1])
            N -= 1
            M -= 1
        else:
            if dp[N][M] == dp[N - 1][M]:
                N -= 1
            else:
                M -= 1

    print (*lst[::-1], sep = '')

if __name__ == '__main__':
    main()

Fixed submission:
S = str(input())
T = str(input())

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')

Buggy python submission (verdict: Time Limit Exceeded):
S = str(input())
T = str(input())

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')

Fixed submission:
S = str(input())
T = str(input())

dp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

for i in range(len(S)):
    for j in range(len(T)):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

lst = []

N = i + 1
M = j + 1
while (N - 1) >= 0 and (M - 1) >= 0:
    if S[N - 1] == T[M - 1]:
        lst.append(S[N - 1])
        N -= 1
        M -= 1
    else:
        if dp[N][M] == dp[N - 1][M]:
            N -= 1
        else:
            M -= 1

print (*lst[::-1], sep = '')
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())

G = [[] for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)

lst = [-1] * (N + 1)


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

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

print (max(lst) - 1)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())

G = [[] for _ in range(N + 1)]

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)

lst = [-1] * (N + 1)


def calc(x):
    if lst[x] != -1:
        return lst[x]
    tmp = 0
    for next_ in G[x]:
        tmp = max(tmp, calc(next_))
    
    lst[x] = tmp + 1
    return tmp + 1

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

print (max(lst) - 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))

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

for i in range(N):
    p = P[i]
    q = 1 - p
    dp[i + 1][0] = dp[i][0] * q
    for j in range(1, i + 2):
        dp[i + 1][j] = dp[i][j - 1] * p + dp[i][j] * q

print (sum(dp[N][(N + 1) // 2:]))

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

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

for i in range(N):
    p = P[i]
    q = 1 - p
    dp[i + 1][0] = dp[i][0] * q
    for j in range(1, i + 2):
        dp[i + 1][j] = dp[i][j - 1] * p + dp[i][j] * q

print (sum(dp[N][(N + 1) // 2:]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] #X - Yの最大値
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] #X - Yの最小値

if N % 2 == 0: #偶数-->最後の一個はY
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        # print (dp2[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])



else: #奇数-->最後の一個はX
    for i in range(N):
        dp1[i][i + 1] = A[i]
        # print (dp1[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])


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

INF = 10 ** 12

dp1 = [[-INF] * (N + 1) for _ in range(N + 1)] #X - Yの最大値
dp2 = [[+INF] * (N + 1) for _ in range(N + 1)] #X - Yの最小値

if N % 2 == 0: #偶数-->最後の一個はY
    for i in range(N):
        dp2[i][i + 1] = -A[i]
        # print (dp2[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 1:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])



else: #奇数-->最後の一個はX
    for i in range(N):
        dp1[i][i + 1] = A[i]
        # print (dp1[i][i + 1], end =' ')
    # print ()
    for k in range(2, N + 1):
        if k % 2 == 0:
            for i in range(N - k + 1):
                dp2[i][i + k] = min(dp1[i][i + k - 1] - A[i + k - 1], dp1[i + 1][i +k] - A[i])
                # print (dp2[i][i + k], end = ' ')
            # print ()
        else:
            for i in range(N - k + 1):
                dp1[i][i + k] = max(dp2[i][i + k - 1] + A[i + k - 1], dp2[i + 1][i + k] + A[i])
                # print (dp1[i][i + k], end = ' ')
            # print ()
    print (dp1[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

if K == 0:
    print (1)
    exit()

dp = [[0] * (K + 1) for _ in range(N + 1)]
for j in range(K + 1):
    dp[N][j] = 1
# dp[N][0] = 1
# print (dp[N])
for i in range(N - 1, -1, -1):
    for j in range(K + 1):
        if j <= A[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = dp[i + 1][j] - dp[i + 1][j - A[i] - 1]
    # print (i)
    # print (dp[i])
    for j in range(K):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD
    # print (dp[i])
    
print ((dp[0][K] - dp[0][K - 1]) % MOD)

Fixed submission:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

if K == 0:
    print (1)
    exit()

dp = [[0] * (K + 1) for _ in range(N + 1)]
for j in range(K + 1):
    dp[N][j] = 1
# dp[N][0] = 1
# print (dp[N])
for i in range(N - 1, -1, -1):
    for j in range(K + 1):
        if j <= A[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = dp[i + 1][j] - dp[i + 1][j - A[i] - 1]
    # print (i)
    # print (dp[i])
    for j in range(K):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD
    # print (dp[i])
    
print ((dp[0][K] - dp[0][K - 1]) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [0] + list(map(int, input().split()))

INF = 10 ** 12

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

for i in range(N):
    A[i + 1] += A[i]

for j in range(1, N):
    for i in range(N - j):
        tmp = INF
        for k in range(i, i + j):
            # print (i, i + j, k + 1)
            tmp = min(tmp, dp[i][k] + dp[k + 1][i + j])
        dp[i][i + j] = tmp + A[i + j + 1] - A[i]

print (dp[0][N - 1])


Fixed submission:
import numpy as np

N = int(input())
A = [0] + list(map(int, input().split()))

A = np.array(A, dtype = np.int64)
A = np.cumsum(A)

dp = np.zeros((N, N), dtype = np.int64)

for j in range(1, N):
    for i in range(N - j):
        # print (dp[i, i:i + j], dp[i + 1:i + j + 1, i + j])
        tmp = min(dp[i, i:i + j] + dp[i + 1:i + j + 1, i + j])
        dp[i][i + j] = tmp + A[i + j + 1] - A[i]

print (dp[0][N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(N)]

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    N = len(matrix[0])
    if n == 0:
        lst = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
        return lst
    lst = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # print (i, j, k)
                lst[i][j] += matrix[i][k] * matrix[k][j]
            lst[i][j] %= mod
    res = mod_pow(lst, n // 2, mod)

    lst = [[0] * N for _ in range(N)]
    if n % 2 == 1:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    lst[i][j] += res[i][k] * matrix[k][j]
                lst[i][j] %= mod
        return lst
    return res 

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i][j]
        ans %= MOD

ans %= MOD
print (ans)

Fixed submission:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(N)]

def mod_pow(matrix, n, mod): #行列累乗を求める
    # print (matrix)
    N = len(matrix[0])
    if n == 0:
        lst = [[1 if i == j else 0 for i in range(N)] for j in range(N)]
        return lst
    lst = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # print (i, j, k)
                lst[i][j] += matrix[i][k] * matrix[k][j]
            lst[i][j] %= mod
    res = mod_pow(lst, n // 2, mod)

    lst = [[0] * N for _ in range(N)]
    if n % 2 == 1:
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    lst[i][j] += res[i][k] * matrix[k][j]
                lst[i][j] %= mod
        return lst
    return res 

matrix = mod_pow(A, K, MOD)
# print (matrix)

ans = 0
for i in range(N):
    for j in range(N):
        ans += matrix[i][j]
        ans %= MOD

ans %= MOD
print (ans)