Problem:
 Score : 100 points    Problem Statement There are N children, numbered 1, 2, \ldots, N .  They have decided to share K candies among themselves.
Here, for each i ( 1 \leq i \leq N ), Child i must receive between 0 and a_i candies (inclusive).
Also, no candies should be left over.  Find the number of ways for them to share candies, modulo 10^9 + 7 .
Here, two ways are said to be different when there exists a child who receives a different number of candies.      Constraints  All values in input are integers.  1 \leq N \leq 100  0 \leq K \leq 10^5  0 \leq a_i \leq K         Input Input is given from Standard Input in the following format:  N  K  a_1  a_2  \ldots  a_N       Output Print the number of ways for the children to share candies, modulo 10^9 + 7 .        Sample Input 1 3 4
1 2 3      Sample Output 1 5  There are five ways for the children to share candies, as follows:   (0, 1, 3)  (0, 2, 2)  (1, 0, 3)  (1, 1, 2)  (1, 2, 1)   Here, in each sequence, the i -th element represents the number of candies that Child i receives.       Sample Input 2 1 10
9      Sample Output 2 0  There may be no ways for the children to share candies.       Sample Input 3 2 0
0 0      Sample Output 3 1  There is one way for the children to share candies, as follows:   (0, 0)        Sample Input 4 4 100000
100000 100000 100000 100000      Sample Output 4 665683269  Be sure to print the answer modulo 10^9 + 7 .

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    A = [0] +a
    a_max = max(A)
    dp = [[0] * (K + 1) for _ in range(N + 1)] 
    mod = 10**9+7
    accum=[0] *(K+2)
    dp[0][0]=1
    for i in range(1,N): 
        lim = A[i] 
        count =0
        for t in range(K+1):
            count +=dp[i-1][t]
            accum[t+1] = count

        for j in range(K+1): 
            dp[i][j] =accum[j+1] -accum[max(j-lim,0)]
            dp[i][j] %=mod


    ans =0
    for i in range(0,A[-1]+1):
        ans +=dp[N-1][K-i]
        ans %=mod

    print(ans)









if __name__ == "__main__":
    main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=1000000007
dp=[[0]*(k+1) for i in range(n+1)] 
dp[0][0]=1
for i in range(n):
  sm=0
  for j in range(k+1):
    sm+=dp[i][j]
    sm%=mod
    dp[i+1][j]=sm
    if j>=a[i]:
      sm-=dp[i][j-a[i]]
      sm=(sm+mod)%mod
print(dp[n][k])

Solution (Python):
import sys
input = sys.stdin.readline

n, k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7

D = [[0] * (k+2) for i in range(n+1)]
D[0][k] = 1
for i in range(1, n+1):
    for j in range(k+1):
        D[i][max(0, j-A[i-1])] = (D[i][max(0, j-A[i-1])] + D[i-1][j]) % mod
        D[i][j+1] = (D[i][j+1] - D[i-1][j]) % mod
    for j in range(1, k+2):
        D[i][j] = (D[i][j] + D[i][j-1]) % mod
print(D[-1][0])

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))

mod=10**9+7
dp=[[0]*(K+1) for i in range(N+1)]
dp[0][0]=1

for i in range(N):
  acc=[0]*(K+2)
  for j in range(K+1):
    acc[j+1]=acc[j]+dp[i][j]
    acc[j+1]%=mod
  for j in range(K+1):
    dp[i+1][j]=acc[j+1]-acc[max(0,j-a[i])]
    dp[i+1][j]%=mod
print(dp[N][K])

Solution (Python):

def resolve():
    MOD = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

    for i in range(N):
        cum = [0]*(K+2)
        for j in range(K + 1):
            cum[j+1] = (cum[j] + dp[i][j]) % MOD
        for j in range(K+1):
            idx = max(0, j - A[i])
            dp[i+1][j] = cum[j+1] - cum[idx]
            dp[i + 1][j] = (dp[i+1][j]+MOD)%MOD

    print(dp[N][K])

if __name__ == "__main__":
    resolve()

Solution (Python):

def resolve():
    MOD = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

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

    for i in range(1, N+1):
        for j in range(1, K+1):
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD
            if j - A[i-1] - 1 >= 0:
                dp[i][j] = dp[i][j] - dp[i-1][j-A[i-1]-1]
                dp[i][j] %= MOD

    print(dp[N][K])


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7









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

Solution (Python):
import sys
readline = sys.stdin.readline

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7





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

Solution (Python):




import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    table = [0] * (K + 1)
    for i in range(XS[0] + 1):
        table[i] = 1

    for i in range(1, N):
        v = 0
        newtable = [0] * (K + 1)
        accum = [0] * (K + 1)
        acc = 0
        for j in range(K + 1):
            acc += table[j]
            accum[j] = acc

        
        
        for j in range(K + 1):
            
            
            
            
            
            
            v = accum[j]
            k = j - XS[i] - 1
            if k >= 0:
                v -= accum[k]

            newtable[j] = v % MOD
        table = newtable

    return table[K]


def main():
    
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))

    print(solve(N, K, XS))



T1 = """
3 4
1 2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


T2 = """
1 10
9
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    0
    """


T3 = """
2 0
0 0
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
4 100000
100000 100000 100000 100000
"""










def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
n, k = map(int, input().split())
lst = list(map(int, input().split()))

ans = 0
MOD = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    sums = [0] * (k+2)
    for j in range(k+1): 
        sums[j+1] = sums[j] + dp[i][j]
        sums[j+1] %= MOD
    for j in range(k+1):
        dp[i+1][j] = sums[j+1] - sums[max(0, j-lst[i])]
        dp[i+1][j] %= MOD 
print(dp[n][k])

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


N, K = na()
a_array = na()
mod = 10 ** 9 + 7

ans = [[0] * (K+1) for _ in range(N)]
total = [[0] * (K+1) for _ in range(N)]

for i in range(a_array[0]+1):
    ans[0][i] = 1
for i in range(K+1):
    total[0][i] = min(i + 1, a_array[0] + 1)


for i in range(1, N):
    for j in range(K+1):
        if j - a_array[i] > 0:
            ans[i][j] = (total[i-1][j] + mod - total[i-1]
                         [j-a_array[i]-1]) % mod
        else:
            ans[i][j] = total[i-1][j]
        if j == 0:
            total[i][j] = ans[i][j]
        else:
            total[i][j] = (total[i][j-1] + ans[i][j]) % mod


print(ans[-1][-1])

Solution (Python):
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for i in range(K+10)] for j in range(N+10)]
mod = int(1e9) + 7
dp[0][0] = 1
for i in range(N):
    pSum = [0 for _ in range(K+10)]
    for j in range(K+1):
        pSum[j + 1] = (pSum[j] + dp[i][j]) % mod
    for j in range(K+1):
        if i >= len(a):
            continue
        dp[i+1][j] = (pSum[j+1] - pSum[max(0, j - a[i])]) % mod
print(dp[N][K])

Solution (Python):
n,k = map(int,input().split())

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

dp = [0] * (k+1)
minimo = [1] * (k+2)

mod = 1e9 + 7

dp[0] = 1
minimo[0] = 0

for i in range(1, n + 1):
    soma = [0] * (k+2)

    for j in range(k+1):
        dp[j] = (minimo[j+1] - minimo[max(0, j - min(k,candies[i-1]))]) % mod
        soma[j+1] = (soma[j] + dp[j]) % mod

    minimo = soma

print(int(dp[k]))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))

dp = [0]*(k+1)
cum = [1]*(k+2)
M = 10**9+7
dp[0] = 1
cum[0] = 0
for i in range(1,n+1):
    current = [0]*(k+2)
    for j in range(k+1):
        dp[j] = (cum[j+1] - cum[max(0, j-min(k,a[i-1]))]) % M
        current[j+1] = (current[j] + dp[j])%M
    cum = current
print(dp[k])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = map(int, input().split())
a = list(map(int, input().split()))

dp = [[0]*(k+1) for _ in range(n+1)]
cum = [1]*(k+2)
M = 10**9+7
for i in range(n+1):
    dp[i][0] = 1
cum[0] = 0
for i in range(1,n+1):
    current = [0]*(k+2)
    for j in range(k+1):

        dp[i][j] = (cum[j+1] - cum[max(0, j-min(k,a[i-1]))]) % M
        current[j+1] = (current[j] + dp[i][j])%M
    cum = current
print(dp[n][k])

Solution (Python):
N, K = map(int, input().split())
*a, = map(int, input().split())

dp = [[1] + [0]*K for _ in range(N)]
for k in range(1, a[0]+1):
    dp[0][k] = 1

for i in range(1, N):
    for k in range(1, K+1):
        if k - a[i] - 1 >= 0:
            dp[i][k] = dp[i][k-1] + dp[i-1][k] - dp[i-1][k-a[i]-1]
        else:
            dp[i][k] = dp[i][k-1] + dp[i-1][k]
        dp[i][k] %= 1e9+7
        
print(int(dp[-1][-1]))

Solution (Python):






import sys
input = sys.stdin.readline


import heapq 
import copy
import math
import decimal











 



 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 
 

def pr_list(a):
	print(*a, sep=" ")
def main():
	
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	def pre(arr):
		ans = [arr[0]]
		for i in range(1,len(arr)):
			ans.append((ans[-1] + arr[i])%mod)
		return ans
	for test in range(tests):
		[n,k] = inlt()
		a = inlt()
		dp = [[0 for j in range(k+1)] for i in range(n)]
		for i in range(0,a[0]+1):
			dp[0][i] = 1
		pre_sum = pre(dp[0])
		for i in range(1,n):
			for j in range(0,k+1):
				lower = max(j - a[i],0)
				dp[i][j] = (pre_sum[j] - pre_sum[lower] + dp[i-1][lower])%mod
			pre_sum = pre(dp[i])
		
		print(dp[-1][-1]) 

				





		
		


if __name__== "__main__":
	main()

Solution (Python):
from itertools import accumulate

def solve():
    MOD = 10**9 + 7

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

    dp = [0] * (K+1)
    dp[0] = 1
    for A in As:
        dp = list(accumulate(dp))
        for j, d in enumerate(dp[:K-A], start=A+1):
            dp[j] -= d
        dp = [dpi % MOD for dpi in dp]

    print(dp[K])


solve()

Solution (Python):
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
I=10**9+7

if sum(a)<k:
    print(0)
    sys.exit()

dp=[[float("inf")]*(k+1) for _ in range(n+1)]
for p in range(k+1):
    dp[0][p]=0
    if a[0]<p:
        dp[1][p]=0
    else:
        dp[1][p]=1
for i in range(1,n):
    s=[0]*(k+2)
    for j in range(k+1):
        s[j+1]=s[j]+dp[i][j]%I
        dp[i+1][j]=s[j+1]-s[max(0,j-a[(i+1)-1])]

print(dp[n][k]%I)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
mod=10**9+7
for i in range(0,a[0]+1):
    dp[i]=1
for i in range(1,len(a)):
    for j in range(1,k+1):
        dp[j]=(dp[j]+dp[j-1])%mod
    for j in range(k,a[i],-1):
        dp[j]=(dp[j]-dp[j-a[i]-1]+mod)%mod
print(dp[k])

Solution (Python):
MOD = 10**9+7

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


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

for i in range(1, N+1):
    for j in range(1, K+1):
        dp[i-1][j] += dp[i-1][j-1]
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j > a[i-1]:
            dp[i][j] -= dp[i-1][j-a[i-1]-1]
        dp[i][j] %= MOD

print((dp[N][K]+MOD)%MOD)

Solution (Python):
MOD = 10**9+7

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


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

upper = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        dp[i-1][j] += dp[i-1][j-1]
    upper += a[i-1]
    for j in range(min(upper, K)+1):
        if j > a[i-1]:
            dp[i][j] = dp[i-1][j] - dp[i-1][j-a[i-1]-1]
        else:
            dp[i][j] = dp[i-1][j]
        dp[i][j] %= MOD

print((dp[N][K]+MOD)%MOD)

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

MOD = pow(10, 9) + 7

dp = [[0 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    S = [0] * (K+1)
    S[0] = dp[i][0]
    
    for j in range(1, K+1):
        S[j] = (dp[i][j] + S[j - 1]) % MOD

    for j in range(K+1):
        if j-1 >= A[i]:
            dp[i+1][j] = (S[j] - S[j-1-A[i]]) % MOD
        else:
            dp[i+1][j] = S[j]

print(dp[N][K])

Solution (Python):
n,k=map(int,input().split())
li=[int(K) for K in input().split()]
dp=[[0 for j in range(k+1)] for i in range(n+1)]
dp[0][0]=1
for b in range(1,n+1):
  dp[b][0]=1
mod=10**9+7  
for i in range(1,n+1):
  sums=[0]*(k+1)
  sums[0]=1
  for j in range(1,k+1):
    sums[j]=(sums[j-1]+dp[i-1][j])%mod
  for a in range(k+1):
    res=sums[a]
    if(a-li[i-1]-1)>=0:
      res=(res-sums[a-li[i-1]-1]+mod)%mod
    dp[i][a]=res
print(dp[n][k])

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))

dp=[[0]*(k+1) for j in range(n+1)]

for i in range(n+1):
    dp[i][0]=1

for i in range(1,n+1):
    for j in range(1,k+1):
        dp[i][j]=dp[i-1][j]+dp[i][j-1]
        if j-a[i-1]-1 >= 0:
            dp[i][j]-=dp[i-1][j-a[i-1]-1]
        dp[i][j]%=mod

print(dp[n][k])

Solution (Python):
def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
    for n in range(N + 1):
        dp[n][0] = 1
    for n in range(1, N + 1):
        dp_left = dp[n][0]  
        for k in range(1, K + 1):
            val = dp_left + dp[n - 1][k]
            kk = k - A[n - 1] - 1
            if kk >= 0:
                val -= dp[n - 1][kk]
            val %= MOD
            dp[n][k] = val
            dp_left = val
    print(dp[N][K])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
MOD=10**9+7
def solve(N:int,K:int,A:list)->int:
    
    dp=[[0]*(K+1) for i in range(N+1)]
    for i in range(N):dp[i][0]=1
    sum=[0]*(K+2)
    for i in range(N):
        for j in range(K+1):
            sum[j+1]=(sum[j]+dp[i][j])%MOD
        for j in range(K+1):
            dp[i+1][j]=(sum[j+1]-sum[max(0,j-A[i])]+MOD)%MOD
            dp[i+1][j]%=MOD
    return dp[N][K]
def main(lines):
    N,K=map(int,lines[0].split())
    A=list(map(int,lines[1].split()))
    print(solve(N,K,A))
if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
dp[0]=1
mod=10**9+7
for i in range(n):
  for j in range(k,0,-1):
    if j>a[i]:dp[j]-=dp[j-a[i]-1]
  for j in range(k):dp[j+1]=(dp[j+1]+dp[j])%mod
print(dp[k])

Solution (Python):
def add(a, b):
    mod = 1e9+7
    return (a+b) % mod
def subtract(a, b):
    mod = 1e9+7
    return (a-b) % mod

n, k = [int(x) for x in input().split()]

arr = [int(x) for x in input().split()]

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

fake = [0 for _ in range(k+2)]

dp[0] = 1

for num in arr:
    
    for i in range(k+1):
        temp = dp[i]
        L = i
        R = min(i+num, k)
        fake[L] = add(fake[L], temp)
        fake[R+1] = subtract(fake[R+1], temp)
        
        
        
        
        
    pref_sum = 0
    
    for i in range(k+1):
        pref_sum = add(pref_sum, fake[i])
        dp[i] = pref_sum
        fake[i] = 0
    

print(int(dp[k]))

Solution (Python):

l=input().split()
n=int(l[0])
k=int(l[1])
l=input().split()
li=[int(i) for i in l]
dp=[[0 for i in range(k+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(1,k+1):
    dp[0][i]=0
pref=[0 for i in range(k+1)]
sumi=0
for i in range(k+1):
    sumi+=dp[0][i]
    pref[i]=sumi
    pref[i]%=1000000007
for i in range(1,n+1):
    for j in range(1,k+1):
        howmany=li[i-1]
        left=max(0,j-howmany)
        right=j
        if(left==0):
            dp[i][j]=pref[j]
        else:
            dp[i][j]=pref[j]-pref[left-1]
        dp[i][j]%=1000000007
    sumi=0
    for j in range(k+1):
        sumi+=dp[i][j]
        pref[j]=sumi
        pref[j]%=1000000007
print(dp[n][k])

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[N][K] = sum(OPT[N-1][K-i]) 0 <= i <= A[N]
    OPT[0][0] = 1
    N*K
    3 4
    1 2 3

1 0 0 0 0
1 1 0 0 0
1 2 2 1 0
1 3 5 6 5

OPT[3][1] = OPT[2][1]+OPT[2][0]
OPT[3][2] = OPT[2][2]+OPT[2][1]+OPT[2][0]
OPT[3][3] = OPT[2][3]+OPT
    """
    N, K = read_ints()
    A = read_ints()
    modulo = 10**9+7
    OPT = [[0]*(K+1) for _ in range(N+1)]
    for i in range(N+1):
        OPT[i][0] = 1
    for j in range(K+1):
        OPT[0][j] = 1
    for i in range(1, N+1):
        for j in range(1, K+1):
            OPT[i][j] += OPT[i][j-1]+OPT[i-1][j]
            if j-A[i-1]-1 >= 0:
                OPT[i][j] -= OPT[i-1][j-A[i-1]-1]
            OPT[i][j] %= modulo
    if K == 0:
        return OPT[-1][-1]
    return (OPT[-1][-1]-OPT[-1][-2])%modulo


if __name__ == '__main__':
    print(solve())

Solution (Python):
from itertools import accumulate

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

dp = [1] + [0] * K
for a in A:
    S = [0] + list(accumulate(dp))
    for i in range(K + 1):
        dp[i] = (S[i + 1] - S[max(0, i - a)]) % mod

print(dp[K])

Solution (Python):
from itertools import accumulate

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

dp = [1] + [0] * K
for a in A:
    S = list(accumulate(dp)) + [0]
    for i in range(K + 1):
        dp[i] = (S[i] - S[max(0, i - a) - 1]) % mod

print(dp[K])

Solution (Python):
mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

dp = [1] + [0] * (K + 1)
for a in A:
    for i in range(1, K + 1):
        dp[i] += dp[i - 1]
    for i in reversed(range(1, K + 1)):
        dp[i] -= dp[max(0, i - a) - 1]
        dp[i] %= mod

print(dp[K])

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 10**9+7

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for j in range(k+1):
    if j == 0:
      dp[i+1][j] = 1
    elif j <= a:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
    else:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a-1]
    dp[i+1][j] %= MOD
ans = dp[n][k]
print(ans)

Solution (Python):
mod=10**9+7
N,K=map(int,input().split())
a = list(map(int,input().split()))
ans=[[0 for e in range(K+1)] for f in range(N+1)]
for e in range(K+1):
 ans[1][e]=min(e+1,a[0]+1)
if N>1:
 for i in range(2,N+1):
  ans[i][0]=1
  for j in range(1,K+1):
   ans[i][j]=ans[i][j-1]+ans[i-1][j]
   if j-a[i-1]-1>=0:
    ans[i][j]-=ans[i-1][j-a[i-1]-1]
   ans[i][j]%=mod
if K==0:
 print(ans[N][K])
else:
 print((ans[N][K]-ans[N][K-1])%mod)

Solution (Python):
large_p = 10**9 + 7
from itertools import accumulate
from itertools import chain
def main():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i1 in range(n):
        accum = tuple(chain([0], accumulate(dp[i1])))
        for i2 in range(k + 1):
            t = max(0, i2 - a[i1])
            dp[i1 + 1][i2] += accum[i2+1] - accum[t] + large_p
            dp[i1 + 1][i2] %= large_p

    print(dp[n][k])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(K+2) for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(N):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][min(K, j+a[i])+1] -= dp[i][j]
        
    dp[i+1][0] %= MOD
    
    for j in range(1, K+2):
        dp[i+1][j] += dp[i+1][j-1]
        dp[i+1][j] %= MOD
    
print(dp[N][K])

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[[0]*(k+1) for _ in range(n+1)]
    dp[0][0]=1
    cum=[0]*(k+2)
    mod=10**9+7
    for i in  range(1,n+1):
        cum[0]=0 
        for j in range(k+1):
            cum[j+1]=cum[j]+dp[i-1][j]
        for j in range(k+1):
            dp[i][j]=(cum[j+1]-cum[max(0,j-A[i-1])])%mod
    print(dp[n][k])
if __name__=='__main__':
    main()

Solution (Python):
from numpy import*
n,k,*a=int_(open(0).read().split())
b=[1]+[0]*k
for i in a:b[i+1:]-=copy(b[:~i]);b=cumsum(b)%(10**9+7)
print(b[k])

Solution (Python):
from numpy import*
n,k,*a=int_(open(0).read().split())
b=int_([1]+[0]*k)
for i in a:b[i+1:]-=copy(b[:~i]);b=cumsum(b)%(10**9+7)
print(b[k])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
d=[[0]*(K+2) for i in range(N+1)]
d[0]=[0]+[1]*(K+1)
m=10**9+7
for i in range(N):
    for j in range(K+1):
        d[i+1][j+1]=(d[i][j+1]-d[i][max(0,j-A[i])]+d[i+1][j])%m
print((d[-1][-1]-d[-1][-2])%m)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 1000000007

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

print(dp[N][K])

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    ni = i + 1
    ruiseki = [0] * (k + 1)
    pre = 0
    for j in range(k + 1):
        ruiseki[j] += pre
        ruiseki[j] += dp[i][j]
        pre = ruiseki[j]
        dp[ni][j] += ruiseki[j]
        if j - A[i] > 0:
            dp[ni][j] -= ruiseki[j - A[i] - 1]
        dp[ni][j] %= mod
print(dp[n][k])

Solution (Python):

MOD = int(1e9)+7


def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))

    
    dp = [[0]*(K+1) for i in range(n+1)]
    prefix = [[0]*(K+1) for i in range(n+1)]
    prefix[0] = [1]*(K+1)
    for i in range(1, n+1):
        for j in range(K+1):
            start = j - min(a[i-1], j)-1
            end = j
            dp[i][j] = (prefix[i-1][end] - \
                (prefix[i-1][start] if start >= 0 else 0))%MOD
            prefix[i][j] = (prefix[i][j-1] + dp[i][j]) % MOD

    print(dp[n][K]%MOD)


if __name__ == "__main__":
    main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]
        dp[i][j] %= 10 ** 9 + 7

print(dp[n][k])

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j == 1:
            dp[i][j] = dp[i - 1][j] + min(a[i - 1], 1)
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]
        dp[i][j] %= 10 ** 9 + 7

print(dp[n][k])

Solution (Python):
import collections
N,K=map(int,input().split())

A=list(map(int,input().split()))
M=10**9+7
dp=[[0]*(K+2)for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=1

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

Solution (Python):
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
MOD=10**9+7
dp=np.zeros((n+1,k+1),dtype=np.int64)
dp[0][0]=1
cnt=1
for i in range(n):
    dp[i+1]=dp[i]
    dp[i+1][a[i-1]+1:]-=dp[i][:-(a[i-1]+1)]
    np.cumsum(dp[i+1],out=dp[i+1])
    dp[i+1]%=MOD
print(dp[n][k])

Solution (Python):
n,k=map(int,input().split())
l=[int(x) for x in input().split()]
dp=[0 for i in range(k+1)]
dp[0]=1
M=10**9+7
for i in range(len(l)):
	p=[0]*(k+1)
	for j in range(k-1,-1,-1):
		li= j+1
		ri=j+min(l[i],k-j)+1
		if li<=ri:
			p[j+1]+=dp[j]
		if ri<=k:
			p[j+min(l[i],k-j)+1]-=dp[j]
		'''for o in range(j+1,j+min(l[i],k-j)+1):
			dp[o]+=dp[j]'''
	su=0
	for i in range(k+1):
		su=(su+p[i])%M
		dp[i]=(dp[i]+su)%M
print(dp[k]%(10**9+7))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in map(int, input().split()):
        
        S = [0] * (k + 2)
        for i in range(k + 1):
            S[i + 1] = S[i] + dp[i]
            if S[i + 1] >= MOD:
                S[i + 1] -= MOD
        
        dp = [(S[i + 1] - S[max(0, i - a)]) % MOD for i in range(k + 1)]

    print(dp[k])
resolve()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,K = LI()
a = [0]+LI()
if K == 0:
    print(1)
    exit(0)
dp = [[1] * (K+1) for _ in range(N+1)]
ac = 0
for i in range(1,N+1):
    ac += a[i]
    s = 0
    for j in range(K+1):
        s += dp[i-1][j]
        if j-a[i]-1 >= 0: s -= dp[i-1][j-a[i]-1]
        dp[i][j] = s % MOD
print((dp[-1][K]-dp[-1][K-1])%MOD)

Solution (Python):
import copy
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
x = [1]*(a[0]+1)+[0]*(k-a[0])
for i in range(1,n):
  oldx = copy.copy(x)
  s = 0
  for j in range(a[i]+1):
    s = (s + oldx[j])%mod
    x[j] = s
  for j in range(a[i]+1,k+1):
    s = (s + oldx[j] -oldx[j-a[i]-1])%mod
    x[j] = s   
print(x[k])

Solution (Python):
n, k = map(int, input().split())
ns = list(map(int, input().split()))
mod = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    b = 0
    cur = [0]
    for j in range(k+1):
        b += dp[i][j] % mod
        cur.append(b)
    for j in range(k+1):
        dp[i+1][j] = (cur[j+1] - cur[max(0, j-ns[i])]) % mod
print(dp[-1][-1])

Solution (Python):
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
    
    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()

Solution (Python):
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
    
    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()

Solution (Python):
import sys
import numpy as np

M = 1000000007  


def solve(N: int, K: int, a):
    dp = np.zeros(K + 1, dtype=np.int64)
    dp[0] = 1
    for x in a:
        cm = np.cumsum(dp)
        dp = cm.copy()
        dp[x + 1 :] -= cm[: -x - 1]
        dp %= M
    return dp[K]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    a = np.array([int(next(tokens)) for _ in range(N)], dtype=np.int64)
    print(solve(N, K, a))


if __name__ == "__main__":
    main()