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 copy
import sys
import numpy as np

MOD = 1000000007  


def debug(s):
    print(s)


def solve(N: int, K: int, a):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        ndp = np.cumsum(dp[i - 1, :])
        dp[i, :] = ndp
        dp[i, ai + 1 :] -= ndp[: -ai - 1]
        dp[i, :] %= MOD
    return dp[N, 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()

Solution (Python):

import copy
import sys

MOD = 1000000007  


def debug(s):
    print(s)


def solve(N: int, K: int, a: "List[int]"):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            
    return dp[N][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 = [int(next(tokens)) for _ in range(N)]  
    print(solve(N, K, a))


if __name__ == "__main__":
    main()

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

m=10**9+7

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

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

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

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

Solution (Python):
import numpy as np

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

MOD = 10 ** 9 + 7

dp = np.zeros(K + 1, dtype=np.int64)
dp[0] = 1
for i in range(1, N + 1):
    S = np.cumsum(dp) % MOD
    dp[:A[i - 1] + 1] = S[:A[i - 1] + 1] % MOD
    dp[A[i - 1] + 1:K + 1] = (S[A[i - 1] + 1:K + 1] - S[:K - A[i - 1]]) % MOD
print(dp[K])

Solution (Python):
import numpy as np

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

MOD = 10 ** 9 + 7

dp = np.zeros((N + 1, K + 1), dtype=np.int64)
dp[0][0] = 1
for i in range(1, N + 1):
    S = np.cumsum(dp[i - 1]) % MOD
    dp[i][:A[i - 1] + 1] = S[:A[i - 1] + 1] % MOD
    dp[i][A[i - 1] + 1:K + 1] = (S[A[i - 1] + 1:K + 1] - S[:K - A[i - 1]]) % MOD
print(dp[N][K])

Solution (Python):
import itertools

N, K = map(int, input().split())
A = tuple(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):
    S = [0] + list(itertools.accumulate(dp[i - 1]))
    for j in range(K + 1):
        dp[i][j] = (S[j + 1] - S[max(0, j - A[i - 1])]) % MOD
print(dp[N][K])

Solution (Python):


def submit():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    modp = 10 ** 9 + 7
    dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

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

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


submit()

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


mod=pow(10,9)+7
dp=[0]*(k+1) 
sdp=[0]*(k+2)
for i in range(a[0]+1):
  dp[i]=1 
for i in range(1,n):
      
      s=0
      for l in range(k+1):
            s+=dp[l]
            sdp[l+1]=s%mod
      for j in range(1,k+1):
        dp[j]=(sdp[1+j]-sdp[max(0,j-a[i])])%mod
print(dp[-1]%mod)

Solution (Python):
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    
    INF = int(1e9)
    mod = int(1e9)+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(n):
        dpsum = [0] * (k + 2)
        for l in range(k + 1):
            dpsum[l + 1] = dpsum[l] + dp[i][l]
            dpsum[l + 1] %= mod
        for j in range(k + 1):
            dp[i + 1][j] = (dpsum[j + 1] - dpsum[max(0, j - a[i])]) % mod
    print(dp[n][k])
    
if __name__ == '__main__':
    main()

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


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

for index1 in range(0,A[1]+1):
    DP[1][index1]=1

for index2 in range(N+1):
    DP[index2][0]=1


for i in range(2,N+1):  
    
    
    C=[0]*(K+2)
    C[1]=DP[i-1][0]%P
    for c in range(2,K+2):
        C[c]=(C[c-1]+DP[i-1][c-1])%P
    for j in range(1,K+1):  
        DP[i][j]=(C[j+1]-C[max(0,j-A[i])])%P




print(DP[N][K]%P)

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

from itertools import groupby, accumulate, product, permutations, combinations

def solve(N,K,A):
    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 = list(map(lambda x:x%mod,accumulate(dp[i-1])))
        for j in range(K+1):
            dp[i][j] = cum[j]
            k = j-A[i-1]
            if k>0:
                dp[i][j] -= cum[k-1]
    ans = dp[N][K]%mod
    return ans
print(solve(N,K,A))

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

Solution (Python):
def main():
    mod = 10**9+7
    n,k = map(int,input().split())
    candies = list(map(int,input().split()))
    dp = [[0 for i in range(k+1)] for j in range(n+1)]
    dp[0][0] = 1
    for pos in range(1,n+1):
        for used in range(k+1):
            a = candies[pos-1]
            start = used
            end = min(start+a+1,k+1)
            dp[pos][start] += dp[pos-1][start]
            if end <= k:
                dp[pos][end] -= dp[pos-1][start]

        for used in range(1,k+1):
            dp[pos][used] += dp[pos][used-1]
            dp[pos][used] %= mod


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


main()

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
if k > sum(a):
    print(0)
    exit()

mod = 1000000007
dp = [[0 for _ in range(k+1)]for __ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 1
for i in range(k+1):
    dp[0][i] = 0

for i in range(1,n+1):
    for j in range(1,k+1):
        if j > a[i-1]:
            if i is 1:
                break
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if j > a[i-1]:
            dp[i][j] -= dp[i-1][j-1-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 for i in range(0,K+1)] for i in range(0,N)]
for i in range(0,K+1):
    if A[0]>=i:
        dp[0][i]=1

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

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

Solution (Python):

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

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

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


MOD = 10**9 + 7
dp = [0]*(k+1)

dp[0] = 1
pref = [0] + [1]*(k+1)
for i in range(n):
    for left in range(k,0,-1):
        dp[left] += pref[left] - pref[left - min(arr[i],left)]
        dp[left] %= MOD
        
        
    pref = [0]
    for e in dp:
        pref.append(pref[-1] + e)

print(dp[k]%MOD)

Solution (Python):
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

mod = 10 ** 9 + 7
dp = [0] * (k + 1)

dp[0] = 1

for i in a:
    neg = [0] * (k + 1)
    s = 0
    dp2 = [0] * (k + 1)
    
    for j in range(k + 1):
        s += dp[j]
        s %= mod
        dp2[j] = s
        neg[min(k, j + i)] += dp[j]
        s -= neg[j]
    
    dp = dp2

print(dp[-1])

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

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

Solution (Python):
mod = 10**9+7
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(K+1) for i in range(N+1)]
S = [0] * (K+2)
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(1,K+2):
        S[j] = (S[j-1] + dp[i-1][j-1])%mod
    for j in range(K+1):
        dp[i][j] = (S[j+1] - S[max(0, j-a[i-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+2) for i in range(n+1)]

from itertools import accumulate
dp[0][k] = 1
for i in range(n):
    x = [0]*(k+2)
    for j in range(k+1):
        x[max(0, j-A[i])] += dp[i][j]%mod
        x[j+1] -= dp[i][j]%mod
    cum = list(accumulate(x))
    dp[i+1] = cum

print(dp[n][0]%mod)

Solution (Python):








'''
3 4
1 2 3
'''

from itertools import accumulate

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

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

dp_cum = [[0] * (K + 2) for i in range(N + 1)]
dp_cum[0] = [0] + [1]*(K+1)

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

    
    for k in range(1, K + 1):
        
        
        
        
        
        

        dp[i][k] = dp_cum[i-1][k+1] - dp_cum[i-1][max(0, k-A[i-1])]

    dp_cum[i] = [0] + list(accumulate(dp[i]))
    dp_cum[i] = [i % DIVISOR for i in dp_cum[i]]




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

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 = [-1] + 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(N):
    for j in range(K):
        if j - a[i+1] >= 0:
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j - a[i+1]]) % MOD
        else:
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]) % MOD

print(dp[N][K])

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

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    
    dp = [0 for _ in range(K+2)]
    dp[0] = 1
    for num in a:
        imos = [0 for _ in range(K+2)]
        for i in range(K+2):
            imos[i] += dp[i]
            imos[min(K+1,i+num+1)] -= dp[i]
        for i in range(K+1):
            imos[i+1] += imos[i]
            imos[i+1] %= MOD
        dp = imos
        
    print(dp[K])
        
if __name__ == "__main__":
    main()

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):
    dpsum = [0]*(k+2)
    for l in range(k+1):
        dpsum[l+1] = dpsum[l] + dp[i][l]
        dpsum[l+1] %= mod
    for j in range(k+1):
        dp[i+1][j] = (dpsum[j+1] - dpsum[max(0,j-a[i])])%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

dp = [0] * (K + 1)
dp[K] = 1
for i in range(N):
  x = a[i]
  imos = [0] * (K + 2)
  for j in range(K + 1):
    if j - x >= 0:
      imos[j - x] += dp[j]
      imos[j - x] %= mod
    else:
      imos[0] += dp[j]
      imos[0] %= mod
    imos[j + 1] -= dp[j]
    imos[j + 1] %= mod
  for j in range(K + 1):
    imos[j + 1] += imos[j]
    imos[j + 1] %= mod
  for j in range(K + 1):
    dp[j] = imos[j]
print(dp[0])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, K = MAP()
a = LIST()

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

Solution (Python):
N,K = map(int,input().split())
a = [0]*110
a[1:] = list(map(int,input().split()))
MOD = 10**9+7
dp = [[0]*110000 for _ in range(110)]
dp_sum = [[0]*110000 for _ in range(110)]
dp[0][0] = 1
for i in range(K+1):
    dp_sum[0][i] = 1

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

        if j-1 >= 0:
            dp_sum[i][j] = dp_sum[i][j-1] + dp[i][j]
        else:
            dp_sum[i][j] = dp[i][j]
        dp[i][j] %= MOD
        dp_sum[i][j] %= MOD
print(dp[N][K])

Solution (Python):
import sys
INF = 10 ** 15
MOD = 10 ** 9 + 7
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import pi
from functools import lru_cache

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    dp = [[0,1] + [0] * k for _ in range(n + 1)]

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

if __name__ =='__main__':
    main()

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

Solution (Python):
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]



n,k = li()
l = sorted(li())
dp = [0]*(k + 1)
helparr = [0] + [1 for i in range(k + 1)]




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

curr = 0
for j in range(k + 1):
    curr += dp[j]
    helparr[j + 1] = curr




for i in l[1:]:
    for j in range(k,-1,-1):
        leftind = max(0,j - i)
        dp[j] = (dp[j] + helparr[j] - helparr[leftind])%mod


    curr = 0
    for j in range(k + 1):
        curr += dp[j]
        helparr[j + 1] = curr



print(dp[-1])

Solution (Python):
N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(K+1) for i in range(N)]
for j in range(a[0]+1):
  dp[0][j]=1
  
for i in range(1,N):
  for j in range(K+1):
    if j==0:
      dp[i][j]=1
    else:
      dp[i][j]=dp[i][j-1]+dp[i-1][j]
      if j>=a[i]+1:
        dp[i][j]-=dp[i-1][j-1-a[i]]
      dp[i][j]=dp[i][j]%(10**9+7)
      
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)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] = (dp[k] + accDp[k] - accDp[max(0, k - a)]) % MOD

print(dp[K] % MOD)

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    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 i in range(N):
        temp = dp[i][0]
        k = a[i]
        for j in range(K+1):
            if j == 0:
                dp[i+1][j] = temp
                continue
            if j <= k:
                temp += dp[i][j]
                dp[i+1][j] = temp%mod
            else:
                temp += dp[i][j] - dp[i][j-k-1]
                dp[i+1][j] = temp%mod
    print(dp[N][K]%mod)


if __name__ == '__main__':
    main()

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












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

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






if sum(A) < K:
  print(0)
  exit(0)

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

M = 10**9 + 7
for i in range(N):
    a = A[i]
    t1 = [0] * (K+1)
    st0 = [0]
    for t in t0:
        st0.append((t + st0[-1]) % M)
    for k in range(K+1):
        l = max(0, k-a)
        t1[k] = (st0[k+1] - st0[l]) % M
    t0 = t1

print(t0[K])

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(k+2) for i in range(n+1)]
dp[0][0]=1
B=[0]*(2*k+3) 
for i in range(1,n+1):
  for j in range(k+1):
    B[j]=B[j-1]+dp[i-1][j]
  for j in range(k+1):
    dp[i][j]=(B[j]-B[j-A[i-1]-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)]

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

for i in range(1, n):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
            if j >= a[i] + 1:
                dp[i][j] -= dp[i-1][j-a[i]-1]
            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()))
dp = [[0 for k in range(K+1)] for n in range(N)]





mod = int(1e9+7)
dp[N-1][0] = 1

for k in range(1, K+1):
	if k > A[N-1]:
		dp[N-1][k] = 0
		
	else:
		dp[N-1][k] = 1
		

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

print(dp[0][K])

Solution (Python):




















N, K = map(int,  input().split())
A = list(map(int,  input().split()))
dp = [[0 for k in range(K+1)] for n in range(N)]





mod = int(1e9+7)
dp[N-1][0] = 1

for k in range(1, K+1):
	if k > A[N-1]:
		dp[N-1][k] = 0
		
	else:
		dp[N-1][k] = 1
		

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

print(dp[0][K])

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 i in range(N):
    ndp = [0] * (K+1)
    ndp[0] = 1
    for j in range(1, K+1):
        ndp[j] = ndp[j-1] + dp[j]
        if j - a[i] - 1 >= 0:
            ndp[j] -= dp[j-a[i]-1]
        ndp[j] %= mod
    dp = ndp
print(dp[K])

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

dp = [[None] * (k + 1) for _ in range(n + 1)]
def dfs(i=0, at=k):
    if dp[i][at] is not None:
        return dp[i][at]

    if i == n:
        r = int(at == 0)
        dp[i][at] = r
        return r

    cnt = 0
    for v in range(a[i] + 1):
        if v > at:
            break
        cnt += dfs(i + 1, at - v)
    dp[i][at] = cnt
    return cnt





def fm(array):
    return ["*" if v is None else v for v in array]

def mod(v):
    if v >= M:
        return v % M
    return v





for i in reversed(range(n + 1)):
    for at in range(k + 1):
        if i == n:
            dp[i][at] = int(at == 0)
            continue
        cnt = 0
        
        
        
        
        cnt = cs[at] - cs[at - min(a[i], at) - 1]
        dp[i][at] = mod(cnt)
        
        
        
    
    cs = list(itertools.accumulate(dp[i])) + [0]
    cs = [mod(v) for v in cs]
    
    
    
print(dp[0][k] % M)

Solution (Python):
from itertools import accumulate

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0] * (K+1)
dp[K] = 1
for a in A:
    temp = [0] * (K+1)
    for k in range(K+1):
        temp[k - min(a, k)] += dp[k]; temp[k - min(a, k)] %= MOD
        temp[k] -= dp[k]; temp[k] %= MOD
    temp = list(accumulate(temp))
    dp = [(d + t) % MOD for d, t in zip(dp, temp)]
print(dp[0] % MOD)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, k = LI()
    a = LI()
    dp = [0] * (k + 1)
    acc = [1] * (k + 1)
    dp[0] = 1
    for i in range(n):
        for l in range(1, k + 1):
            dp[l] = acc[l]
            dp[l] -= acc[l - a[i] - 1] if l - a[i] > 0 else 0
            dp[l] %= mod
        for l in range(1, k + 1):
            acc[l] = acc[l - 1] + dp[l]
            acc[l] %= mod
    print(dp[-1])


    return



if __name__ == '__main__':
    solve()

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

import numpy as np

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

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

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

for i in range(N - 1, -1, -1):
    dp[i:i + 1, :A[i] + 1] = dp[i + 1:i + 2, :A[i] + 1]
    dp[i:i + 1, A[i] + 1:] = dp[i + 1:i + 2, A[i] + 1:] - dp[i + 1:i + 2, :K - A[i]]
    
    dp[i] = np.cumsum(dp[i]) % MOD
    

print ((dp[0, K] - dp[0, K - 1]) % MOD)

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


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]
    
    
    for j in range(K):
        dp[i][j + 1] += dp[i][j]
        dp[i][j + 1] %= MOD
    
    
print ((dp[0][K] - dp[0][K - 1]) % MOD)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0]*(k+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  ai = A[i-1]
  now = 0
  for ki in range(k+1):
    now += dp[i-1][ki]
    if ki - ai > 0:
      now -= dp[i-1][ki-ai-1]
    dp[i][ki] = now % mod
print(dp[n][k])

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

n,k=LI()
a=LI()

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

m=0
for i in range(n):
    b=[0]*(k+2)
    for x in range(k+1):
        b[x+1]=b[x]+dp[i][x]
        b[x+1]%=mo
    m+=a[i]
    for x in range(k+1):
        dp[i+1][x]=b[x+1]-b[max(0,x-a[i])]

ans=(dp[n][k]%mo)
print(ans)