Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    s = [1]*(K+2)
    s[-1] = 0
    tmp = 0
    for i in range(1, N+1):
        next = [0]*(K+2)
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp
            next[j] = (next[j+1]+tmp) % mod
        s = list(next)

    print(tmp)


main()


Fixed submission:
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    s = [1]*(K+2)
    s[-1] = 0
    for i in range(1, N+1):
        tmp = 0
        next = [0]*(K+2)
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp
            next[j] = (next[j+1]+tmp) % mod
        s = list(next)

    print(dp[-1][0])


main()


Fixed submission:
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    s = [0]*(K+2)
    for i in range(1, N+1):
        tmp = 0
        for j in range(K, -1, -1):
            s[j] = (s[j+1] + dp[i-1][j]) % mod
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()


Fixed submission:
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

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


Fixed submission:
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()