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):
def main():
  M=10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[1]+[0]*k]
  for b,i in zip(dp,a):
    t,d=0,[]
    for v in b[:i+1]:
      t+=v
      t%=M
      d+=t,
    for w,v in zip(b,b[i+1:]):
      t+=v-w
      t%=M
      d+=t,
    dp+=d,
  print(t)
main()

Solution (Python):
def main():
  M=10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[1]+[0]*k]
  for b,i in zip(dp,a):
    t,d=0,[]
    for v in b[:i+1]:
      t+=v
      t%=M
      d+=t,
    for w,v in zip(b,b[i+1:]):
      t+=v-w
      t%=M
      d+=t,
    dp+=d,
  print(t)
main()

Solution (Python):
def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
    t=0
    for j,v in e(b):
      t+=v
      if j>a:t-=b[~a+j]
      t%=M
      d[j]=t
  print(t)
main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
(1+x+...+x^a) をたくさんかける
(1-x^{a+1}) をかけて、(1-x)^{-1}をかける
"""

import numpy as np
MOD = 10 ** 9 + 7
N,K = map(int,input().split())
dp = np.zeros(K+1, dtype=np.int64)
dp[0] = 1

for a in map(int,input().split()):
    
    prev = dp.copy()
    dp[a+1:] -= prev[:-(a+1)]
    np.cumsum(dp, out=dp)
    dp %= MOD

answer = dp[K]
print(answer)

Solution (Python):
def solve():
    k, a = read()
    result = think(k, a)
    write(result)


def read():
    n, k = read_int(2)
    return k, read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(k, a):
    mode = 10 ** 9 + 7
    n = len(a)

    
    
    dp = [[0 for x in range(k + 1)] for y in range(n)]
    dp[0][0] = 1

    accumulated_a = [0 for x in range(n)]
    accumulated_a[0] = a[0]
    for i in range(1, n):
        accumulated_a[i] = accumulated_a[i - 1] + a[i]

    if accumulated_a[n - 1] < k:
        return 0

    accumulated_dp = [0] * (k + 2)

    
    
    
    
    

    for i in range(n):
        for j in range(min(accumulated_a[i] + 1, k + 1)):
            if i == 0 and j == 0:
                continue
            if i == 0:
                if j <= a[i]:
                    dp[i][j] = 1
            else:
                
                dp[i][j] += accumulated_dp[j + 1] - accumulated_dp[max(j - a[i], 0)]
                dp[i][j] %= mode

        for y in range(k + 1):
            accumulated_dp[y + 1] = accumulated_dp[y] + dp[i][y]

    return dp[n - 1][k]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
MAX_INT = int(10e2)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

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

aa = a[0]
num = 0
for i in range(K+1):
  if i <= aa:
    dp[1][i] = 1
    num += 1
  Cs[1][i] = num
for i in range(2,N+1):
  num = 0
  for j in range(K+1):
    if j-a[i-1]-1 < 0:
      dp[i][j] = Cs[i-1][j] %mod
    else:
      dp[i][j] = (Cs[i-1][j] - Cs[i-1][j-a[i-1]-1]) %mod
    num += dp[i][j]
    Cs[i][j] = num

print(dp[N][K] %mod)

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

MOD = 10 ** 9 + 7
DP = [[0] * (K + 1) for _ in range(N)]

for i in range(a[0] + 1):
  DP[0][i] = 1

L = [0] * (K + 1)
for i in range(1, N):
  L[0] = 1
  for j in range(1, K + 1):
    L[j] = (DP[i - 1][j] + L[j - 1]) % MOD
  x = a[i]
  for j in range(K + 1):
    if j <= x:
      DP[i][j] = L[j]
    else:
      DP[i][j] = L[j] - L[j - x - 1]
      while DP[i][j] < MOD:
        DP[i][j] += MOD

print(DP[N - 1][K] % MOD)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random 

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, K = LI()
a = LI()
"""

dp = np.zeros(K+1, dtype=np.int64)
dp[0:a[0]+1] = 1

for i in range(1,N):
    acc = np.cumsum(dp)
    for j in range(K+1)[::-1]:
        if (j-a[i]<=0):
            dp[j] = acc[j]%mod
        else:
            dp[j] = (acc[j] - acc[j-a[i]-1])%mod

print(dp[K])

"""
dp = [0]*(K+1)
acc = [0]*(K+2)

for i in range(K+1):
    if (i <= a[0]):
        dp[i] =  1
    acc[i+1] = acc[i] + dp[i]

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

    acc[0] = 0
    for j in range(K+1):
        acc[j+1] = (acc[j] + dp[j])%mod

print(dp[K])

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N,K = inpl()
aa = inpl()

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





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

for i in range(1,N):
    tmp = 0
    rdp = [0]*(K+2)
    for k in range(K+1):
        tmp += dp[i-1][k]
        tmp %= mod
        rdp[k+1] = tmp

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

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

Solution (Python):

N,K=list(map(int,input().strip().split(' ')))
A=list(map(int,input().strip().split(' ')))
dp=[[0] * (K+1)  for i in range(N)]
for i in range(min(A[0]+1,K+1)):
    dp[0][i]=1
for i in range(N):
    dp[i][0]=1
MOD=10**9+7
for i in range(1,N):
    pre=[]
    temp=0
    for j in range(K+1):
        temp+=dp[i-1][j]
        temp%=MOD
        pre+=[temp]
        
    for j in range(1,K+1):
        
        
        temp=0
        if j-A[i]>0:
            temp=pre[j-A[i]-1]
        dp[i][j]=pre[j]-temp
        dp[i][j]%=MOD

print(dp[-1][K])

Solution (Python):


import sys

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

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

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

        
        
        pre = [[0] * (n + 1) for _ in range(k + 2)]
        for i in range(n + 1):
            pre[0][i] = 1
        for v in range(1, k + 1):
            pre[v][0] = pre[v - 1][0]
            for i in range(1, n + 1):
                dp[v][i] += (pre[v][i - 1] - pre[v - min(v, a[i - 1]) - 1][i - 1]) % MOD
                pre[v][i] = pre[v - 1][i] + dp[v][i]

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

solver = MCandies()
input = sys.stdin.readline

solver.solve()

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

def accmulate(array):
    cs = [0]*(len(array)+1)
    for i in range(len(array)):
        cs[i+1] = cs[i] + array[i]
    return cs

def query(l,r):
    return cs[r+1] - cs[l]

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):
    cs = accmulate(dp[i-1])
    for j in range(K+1):
        dp[i][j] += query(max(j-A[i-1], 0), j)
        dp[i][j] %= mod

ans = dp[N][K]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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 n in range(1, N + 1):
	
	cum = [0] * (K + 2)
	for k in range(K + 1):
		cum[k + 1] = cum[k] + dp[n - 1][k]
		dp[n][k] = cum[k + 1] - cum[max(0, k - a[n - 1])]
		dp[n][k] %= mod

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

Solution (Python):
import fileinput


def solve_candies(ch_count, total_canides, capacity_list):
    mod = 10**9 + 7
    last_solutions = [0] * (total_canides + 1)
    last_solutions[0] = 1

    all_total = 0
    for current_child in range(ch_count):
        current_cap = capacity_list[current_child]

        new_total = min(all_total + current_cap, total_canides)

        current_solutions = [0] * (total_canides + 1)

        current_sum = 0
        summed_candies = 0

        for total in range(new_total + 1):
            current_sum += last_solutions[total]
            summed_candies += 1
            if summed_candies > current_cap + 1:
                current_sum -= last_solutions[total - current_cap - 1]

            current_solutions[total] = current_sum % mod

        last_solutions = current_solutions
        all_total = new_total

    return last_solutions[-1]


inp = fileinput.FileInput()

split = inp.readline().split(" ")
children = int(split[0])
total_candies = int(split[1])
caps = [int(v) for v in inp.readline().split()]

print(solve_candies(children, total_candies, caps))

Solution (Python):
mod = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))

dp = [0]*(K+1)
dp[0] = 1
for a in A:
    dp2 = [0]*(K+1)
    for i in range(K+1):
        dp2[i] += dp[i]
        if i + a + 1 <= K:
            dp2[i+a+1] -= dp[i]
    for i in range(1, K+1):
        dp2[i] = (dp2[i-1] + dp2[i]) % mod
    dp = dp2[:]
print(dp[-1])

Solution (Python):


MOD=10**9+7

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

dp=[0]*(2*k+1)
dp[0]=1
for a in aa:
    l=k-a
    s=sum(dp[l:k+1])%MOD
    for i in range(k,-1,-1):

        s-=dp[i]
        s%=MOD
        dp[i] += s
        l-=1
        s+=dp[l]

        
    
print(dp[k]%MOD)

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)]

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

for i in range(2, 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]:
            dp[i][j] -= (dp[i - 1][j - a[i - 1] - 1]) % mod
        dp[i][j] %= mod
print(dp[n][k])

Solution (Python):
import numpy as np


def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = np.zeros(k + 1, dtype=np.int64)
    dp[0] = 1
    for a in a_s[:-1]:
        dp = np.cumsum(dp) % md
        if k != a:
            dp[k:a:-1] = (dp[k:a:-1] - dp[k - a - 1::-1]) % md
    return np.sum(dp[k - a_s[-1]:]) % md


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

Solution (Python):
def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


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

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
dp = []
for i in range(N):
  L = [0]*(K+1)
  dp.append(L)
for i in range(A[0]+1):
  dp[0][i] = 1
for i in range(1,N):
  cur = [0]*(K+2)
  for j in range(K+1):
    cur[j+1] = (cur[j]+dp[i-1][j])%(10**9+7)
  for k in range(K+1):
    if k > A[i]:
      dp[i][k] = cur[k+1]-cur[k-A[i]]
    else:
      dp[i][k] = cur[k+1]
print(dp[N-1][K]%(10**9+7))

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

MOD = 10 ** 9 + 7

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

dp[0][0] = 1
for j in range(1, a[0] + 1):
    dp[0][j] = 1

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

print(dp[n-1][k])

Solution (Python):


from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        
        
        
        dp = list(accum(dp))
        
        
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

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

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
A=tuple(map(int,input().split()))
DP=[[0]*(k+1) for _ in range(n)]
acc=[0]*(k+2)
for i in range(k+1):
    if i<=A[0]:
        DP[0][i]=1
    acc[i+1]=acc[i]+DP[0][i]
for i in range(1,n):
    for j in range(k+1):
        DP[i][j]=(acc[j+1]-acc[max(0,j-A[i])])%mod
    acc[0]=0
    for j in range(k+1):
        acc[j+1]=(acc[j]+DP[i][j])%mod
print(DP[-1][-1])

Solution (Python):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod =10**9+7


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

b = [0]*(k+2)

for i in range(k+1):
    if i <= a[0]:
        dp[0][i] = 1
    b[i+1] = b[i]+dp[0][i] 

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

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) ]
acc = [ [0]*(K+1) for _ in range(N) ]
mn = min(K,a[0])

for i in range(K+1):
    if i <= mn:
        dp[0][i] = 1
    acc[0][i] = (acc[0][i-1] + dp[0][i])%mod if i > 0 else dp[0][i]%mod

for i in range(1,N):
    dp[i][0] = dp[i-1][0]
    acc[i][0] = dp[i][0]
    for k in range(1,K+1):
        if k - a[i] <= 0:
            dp[i][k] = acc[i-1][k]  % mod 
        else:
            dp[i][k] = (acc[i-1][k] - acc[i-1][k-a[i]-1]) % mod
        acc[i][k] = (acc[i][k-1] + dp[i][k])%mod

print(dp[N-1][K]%mod)

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


dp = [[0]*(k+2) for i in range(n)]
for j in range(1,k+2):
  if j-1 <= a[0] : 
    dp[0][j] = dp[0][j-1] + 1
  else:
    dp[0][j] = dp[0][j-1] + 0

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

print((dp[n-1][k+1]-dp[n-1][k])%mod)

Solution (Python):

import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  
	for k in range( min (K+1,a+l) ):
		
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

Solution (Python):
n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
p = 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(n):
    for j in range(k):
        DP[i+1][j+1] = DP[i + 1][j]
        DP[i+1][j+1] += DP[i][j+1]
        if j - A[i] >= 0: DP[i+1][j+1] -= DP[i][j - A[i]]
        DP[i+1][j+1] %= p
    
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(1, n+1):
    
    
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= 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(1, n+1):
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])

Solution (Python):
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
P = 10**9+7
def cumsum(A):
    B = [A[0]]
    for i in range(1, len(A)):
        B.append((B[-1]+A[i])%P)
    return B

dp = [1] + [0] * (K+N)
for a in A:
    dp = [(dp[i]-(dp[i-a-1] if i>=a+1 else 0))%P for i in range(K+1)]
    dp = cumsum(dp)
print(dp[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 _ in range(N+1)]
    dp[0][K] = 1

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


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import accumulate

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

mod = 10 ** 9 + 7

dp = [0] * (K + 1)
dp[0] = 1

for i in range(N):
    acc_dp = [0] + list(accumulate(dp))

    cand_dp = [0] * (K + 1)
    for k in range(K + 1):
        cand_dp[k] = acc_dp[k + 1] - acc_dp[max(0, k - a_list[i])]
        cand_dp[k] %= mod
    dp = cand_dp
print(dp[K])

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

MOD = 10**9+7
N, K = map(int,input().split())
*a, = map(int,input().split())

p = list(accumulate(a))

dp = [0] * (K+1)
dp[0] = 1
prefix = [0]+[1]*(K+1)
for i in range(N):
    new_dp = [0]*(K+1)
    for j in range(min(p[i],K)+1):
        new_dp[j] = prefix[j+1] - prefix[max(0,j-a[i])]
    dp = new_dp[:]
    prefix = [i % MOD for i in [0]+list(accumulate(dp))]

print(dp[K]%MOD)

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

MOD = 10**9+7
N, K = map(int,input().split())
a = list(map(int,input().split()))

p = list(accumulate(a))

dp = [0] * (K+1)
dp[0] = 1
prefix = [0]+[1]*(K+1)
for i in range(N):
    new_dp = [0]*(K+1)
    for j in range(min(p[i],K)+1):
        new_dp[j] = prefix[j+1] - prefix[max(0,j-a[i])]
    dp = new_dp[:]
    prefix = [i % MOD for i in [0]+list(accumulate(dp))]

print(dp[K]%MOD)

Solution (Python):
from itertools import accumulate

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

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

MOD = int(1e9+7)

dp = [0] * (K+1)
dp[0] = 1

for n in range(N):

    sumlist = [0]
    sumlist += dp[:]
    sumlist = list(accumulate(sumlist))

    ndp = [0] * (K+1)
    for k in range(K+1):
        ndp[k] = sumlist[k+1] - sumlist[max(0, k - A[n])] 
        ndp[k] %= MOD
    dp = ndp
                
print(dp[K]%MOD)

Solution (Python):
from itertools import accumulate

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

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

MOD = int(1e9+7)

dp = [0] * (K+1)
dp[0] = 1

for n in range(N):

    sumlist = [0]
    sumlist += dp[:]
    sumlist = list(accumulate(sumlist))

    ndp = [0] * (K+1)
    for k in range(K+1):
        ndp[k] = sumlist[k+1] - sumlist[max(0, k - A[n])] 
        ndp[k] %= MOD
    dp = ndp
                
print(dp[K]%MOD)

Solution (Python):


MOD = 1000000007

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())

dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    suma = 0
    l = 0
    r = 0
    for j in range(k + 1):
        if l < j - a[i - 1]:
            suma -= dp[i - 1][l]
            l += 1
        if r <= j:
            suma += dp[i - 1][r]
            r += 1
        suma %= MOD
        dp[i][j] += suma
        dp[i][j] %= MOD
print(dp[n][k])

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    

print(NOW[K])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    l = k + 1

    y = [1] * (a[-1]+1) + [0] * (l-a[-1]-1)

    for i in range(n-2,-1,-1):
        z = [None] * l
        s = 0
        c = a[i] + 1
        for j in range(c):
            z[j] = s = (s + y[j]) % mod

        for j in range(c,l):
            z[j] = s = (s + y[j] - y[j-c]) % mod

        y = z

    return (y[-1] + mod) % mod


print(main())

Solution (Python):
N,K = map(int,input().split())
A = map(int,input().split())
MOD = 10**9 + 7

dp = [0]*(1+K)
dp[0] = 1

for a in A:
  t,dp[K] = dp[K], sum(dp[j] for j in range(K-a,K+1)) % MOD

  for i in reversed(range(K)):
    t,dp[i] = dp[i], (dp[i+1]-t+(dp[i-a] if i >= a else 0)) % MOD

print(dp[K])

Solution (Python):
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*(K+1)
dp[0] = 1
MOD = 10**9 + 7
for i in range(N):
    c = sum(dp[K-A[i]:K+1]) % MOD
    for j in range(K, -1, -1):
        v = dp[j]
        dp[j] = c
        c -= v
        if j-A[i]-1 >= 0:
            c += dp[j-A[i]-1]
        c %= MOD
print(dp[K])

Solution (Python):
from itertools import accumulate

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
MOD = 10**9+7

for i,a in enumerate(A):
    ac = [0] + list(accumulate(dp[i]))
    for j in range(K+1):
        dp[i+1][j] = (ac[j+1] - ac[max(0,j-a)]) % MOD
print(dp[-1][-1])

Solution (Python):
from itertools import accumulate, starmap
from operator import sub

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [0] * (k + 1)
dp[0] = 1
for a in aaa:
    dp = list(accumulate(dp))
    dp[a + 1:] = starmap(sub, zip(dp[a + 1:], dp[:-a - 1]))
    dp = [x % MOD for x in dp]
print(dp[k])

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dp=[[0]*(K+1) for i in range(N+1)]
sumi=[[0]*(K+2) for i in range(N+1)]
mod=10**9+7
dp[0][K]=1
sumi[0][K+1]=1
sumi
for i in range(1,N+1):
    for k in range(K+1):
        
        dp[i][k]=sumi[i-1][min(k+A[i-1],K)+1]-sumi[i-1][k]
        dp[i][k]%=mod
        sumi[i][k+1]=sumi[i][k]+dp[i][k]
        sumi[i][k+1]%=mod
print(dp[N][0]%mod)

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 j in range(1,n+1):
  rui = [0] * (k+2)
  for i in range(k+1):
    rui[i+1] += rui[i] + dp[j-1][i]
  for i in range(k+1):
    if i - a[j-1] >= 0:
      dp[j][i] = (rui[i+1] - rui[i-a[j-1]])%mod
    else:
      dp[j][i] = rui[i+1]%mod
print(dp[n][k]%mod)

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

def make_sum(i):
	for j in range(k+1):
		sum_list[i].append((sum_list[i][-1] + dp[i][j]) % MOD)
	return

for j in range(a[0]+1):
	dp[0][j] = 1

for i in range(1, n):
	make_sum(i-1)
	for j in range(k+1):
		dp[i][j] = (sum_list[i-1][j+1] - sum_list[i-1][max(0, j-a[i])]) % MOD

print(dp[n-1][k])

Solution (Python):
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mod=10**9+7
dp=[[0]*(K+1) for i in range(N+1)]
dp[0][0]=1
dp_sum=[[0]*(K+2) for i in range(N+1)]
dp_sum[0]=[0]+[1]*(K+1)
for i in range(N):
  for k in range(K+1):
    dp[i+1][k]=(dp_sum[i][k+1]-dp_sum[i][max(k-a[i],0)])%mod
    dp_sum[i+1][k+1]=(dp_sum[i+1][k]+dp[i+1][k])%mod
print(dp[N][K])

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,k = li()
a = list(li())
MOD = 10**9+7

dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(k+1):
    if i <= a[0]:
        dp[1][i] = 1

if n > 1:   
    dp[1] = list(accumulate(dp[1]))
        
for i in range(1,n+1):
    dp[i][0] = 1
    
for i in range(2,n+1):
    for m in range(1,k+1):
        if m-a[i-1] > 0:
            dp[i][m] = dp[i-1][m] - dp[i-1][m-a[i-1]-1]
        else:
            dp[i][m] = dp[i-1][m]
        dp[i][m] %= MOD
    
    if i < n:
        dp[i] = list(accumulate(dp[i]))
        
print(dp[n][k])

Solution (Python):
from itertools import accumulate

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:
    accDP = [0] + list(accumulate(dp))
    accDP = [accDPi % MOD for accDPi in accDP]
    dp = [(accDP[j+1] - accDP[max(0, j-A)]) % MOD for j in range(K+1)]

print(dp[K])