Buggy python submission (verdict: Time Limit Exceeded):
def f(k, A):
    n = len(A)

    prev = [0] * (k + 1)
    cur = [0] * (k + 1)

    # init for last column
    for j in range(min(A[n - 1], k) + 1):
        prev[j] = 1

    for i in range(n - 2, -1, -1):
        kount = 0
        for j in range(k + 1):
            # dp[i][j] = SUM dp[i - 1][ ...A[i] items before j...]
            kount += prev[j]
            if j > A[i]:
                kount -= prev[j - A[i] - 1]
            cur[j] = kount
        prev, cur = cur, prev

    return prev[-1] % 1000000007

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
#assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = f(k, A)
print(ans)


Fixed submission:
from itertools import accumulate

def f(k, A):
    n = len(A)

    mod = int(1e9 + 7)
    dp = [0] * (k + 1)

    # init for last column
    for j in range(min(A[n - 1], k) + 1):
        dp[j] = 1

    for i in range(n - 2, -1, -1):
        dp = list(accumulate(dp))
        a = A[i]
        dp[a+1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]

    return dp[-1] % mod

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = f(k, A)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def f(k, A):
    n = len(A)
    dp = [ [0] * (k+1) for _ in range(n) ]

    # init for last column
    for j in range(min(A[n - 1] + 1, k + 1)):
        dp[n - 1][j] = 1

    for i in range(n - 2, -1, -1):
        kount = 0
        for j in range(k + 1):
            # dp[i][j] = SUM dp[i - 1][ ...A[i] items before j...]
            # start = j - A[i]
            # if start < 0:
            #     start = 0
            # X = dp[i + 1][start:j + 1]
            # count = sum(X)
            kount += dp[i+1][j]
            if j > A[i]:
                kount -= dp[i+1][j - A[i] - 1]
#            assert kount == count
            assert dp[i][j] == 0
            dp[i][j] = kount

    return dp[0][-1] % 1000000007

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = f(k, A)
print(ans)


Fixed submission:
from itertools import accumulate

def f(k, A):
    n = len(A)

    mod = int(1e9 + 7)
    dp = [0] * (k + 1)

    # init for last column
    for j in range(min(A[n - 1], k) + 1):
        dp[j] = 1

    for i in range(n - 2, -1, -1):
        dp = list(accumulate(dp))
        a = A[i]
        dp[a+1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]

    return dp[-1] % mod

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

n, k = map(int, input().split())
A = list(map(int, input().split()))
ans = f(k, A)
print(ans)