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
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):
p = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
dq = [[0 for _ in range(K+2)] for _ in range(N+1)]
for j in range(K+1):
    if j>A[N]:
        dp[N][j] = 0
    else:
        dp[N][j] = 1
    dq[N][j+1] = (dq[N][j]+dp[N][j])%p
for i in range(N-1,0,-1):
    for j in range(K+1):
        dp[i][j] = (dq[i+1][j+1]-dq[i+1][max(0,j-A[i])])%p
        dq[i][j+1] = (dq[i][j]+dp[i][j])%p
print(dp[1][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):
    fake = [0] * (k + 1)
    for used in range(k, -1, -1):
        tmp = dp[used]
        L = used + 1
        R = used + min(a[i], k - used)
        if L <= R:
            fake[L] = (fake[L] + tmp) % MOD
            if R + 1 <= k:
                fake[R + 1] = (fake[R + 1] - tmp + MOD) % MOD
    prefix_sum = 0
    for j in range(k + 1):
        prefix_sum = (prefix_sum + fake[j]) % MOD
        dp[j] = (dp[j] + prefix_sum) % MOD
print(dp[k])

Solution (Python):
def p_m():
    n, k = map(int, input().split())
    *a, = 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(1, n + 1):
        for j in range(1, k + 1):
            if j - 1 - a[i - 1] >= 0:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1 - a[i - 1]]) % mod
            else:
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod
    print(dp[n][k])


if __name__ == '__main__':
    p_m()

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) 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-1-a[i-1]>=0:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i-1]])%mod
        
        else:
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod

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

Solution (Python):
def cumsum(inlist):
    s = 0
    outlist = [0]
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist

mod = 10**9+7
n, k = [ int(v) for v in input().split() ]
a_list = [ int(v) for v in input().split() ]

dp_list = [ 0 for i in range(k+1) ]
dp_list[0] = 1

for i in range(n):
    cum_dp_list = cumsum(dp_list)

    new_dp_list = [ 0 for i in range(k+1) ]
    for j in range(k+1):
        r = min(j+1,k+1)
        l = max(0,j-a_list[i]) 
        new_dp_list[j] = cum_dp_list[r] - cum_dp_list[l]
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[-1])

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

MOD = int(pow(10, 9) + 7)

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

for c in range(1, N+1):
    for r in range(K, -1, -1):
        lo = dp[c - 1][r]
        hi = dp[c - 1][r + candies[c - 1] + 1] if r + candies[c - 1] + 1 <= K else 0
        dp[c][r] = (lo - hi) + (dp[c][r+1] if r + 1 <= K else 0)
        dp[c][r] %= MOD

def pprint(table):
    for i, row in enumerate(table):
        print([row[j] - row[j+1] for j in range(K)] + [row[K]])



print((dp[N][0] - (dp[N][1] if K > 0 else 0)) % MOD)

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

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = map(int, input().split())
    u = [1] + [0] * K
    v = [1] + [0] * K
    s = 1
    for a in A:
        u, v = v, u
        s += a
        c = 0
        for i, t in enumerate(u[:a + 1]):
            c += t
            v[i] = c
        for i, t, tt in zip(range(a + 1, K + 1), u[a + 1:s], u):
            c += t - tt
            v[i] = c
    print(v[K] % (10 ** 9 + 7))

main()

Solution (Python):
def main():
    N, K = map(int, input().split())
    a = tuple(map(int, input().split()))
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in a[1:]:
        lt, l = l, lt
        s += i
        l[0] = 1
        t = 1
        for j in range(1, i+1):
                t += lt[j]
                l[j] = t
        for j in range(i+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - i - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [0] * (K+1)
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    u = [1] + [0] * K
    v = [1] + [0] * K
    s = 0
    for i in A:
        u, v = v, u
        s += i
        t = 0
        for k in range(i):
            t += u[k]
            v[k] = t
        for k in range(i, min(s, K) + 1):
            t += u[k]
            v[k] = t
            t -= u[k - i]
    print(v[K] % (10 ** 9 + 7))

main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

main()

Solution (Python):
def candies(n,k,a): 
    mod=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+1][j-1]+dp[i][j]-dp[i][j-1-a[i]] +mod ) % mod
            else:
                dp[i+1][j]=( dp[i+1][j-1]+dp[i][j] ) %mod
    print(dp[n][k])


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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
n, k = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
memo_ls = [[0 for i in range(k+1)] for j in range(n)]
memo_ls[0][0] = 1
for i in range(n):
    for j in range(k+1):
        if i == 0:
            if j <= a_ls[i]:
                memo_ls[i][j] = 1
            continue
        if j == 0:
            memo_ls[i][j] = 1
            continue
        if a_ls[i] < j:
            memo_ls[i][j] = (- memo_ls[i-1][max(0,j-a_ls[i]-1)] + memo_ls[i][j-1] + memo_ls[i-1][j]) % (10**9+7) 
        else:
            memo_ls[i][j] = (memo_ls[i][j-1] + memo_ls[i-1][j]) % (10**9+7)
print(memo_ls[-1][-1])

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

import numpy as np

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

MOD = 10**9 + 7

"""
・次々と(1+x+...+x^a)をかけていく
・(1-x^{a+1})をかけたあと(1-x)^{-1}をかける
"""

dp = np.zeros(K+10,np.int64)
dp[0] = 1
for a in A:
    dp[(a+1):] -= dp[:-(a+1)].copy()
    dp %= MOD

for _ in range(N):
    np.cumsum(dp,out=dp); dp %= MOD

answer = dp[K]
print(answer)

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())
    A=list(map(int,input().split()))
    dp=[0]*(k+1)
    dp[k]=1
    for i in range(n):
        ndp=[0]*(k+1)
        
        S=[0]*(k+2)
        for j in range(k+1):
            S[j+1]=S[j]+dp[j]
            S[j+1]%=MOD
        
        for j in range(k+1):
            ndp[j]=S[min(j+A[i]+1,k+1)]-S[j]
            ndp[j]%=MOD
        dp=ndp
    print(dp[0])
resolve()

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 i in range(n)]

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

sum_a = []
now = 0
for i in a:
    now += i
    sum_a.append(now)

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

        dp[i][j] %= mod
        


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

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

for i in range(K+1):
  if A[0] >= i:
    dp[0][i] = 1

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

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    lst = [0] + list(accumulate(dp[i-1]))
    for j in range(k+1):
        if j - a[i-1] < 0:
            dp[i][j] += lst[j+1] - lst[0]
            dp[i][j] %= mod
        else:
            dp[i][j] += lst[j+1] - lst[j-a[i-1]]
            dp[i][j] %= mod
print(dp[-1][-1])

Solution (Python):
from itertools import accumulate

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

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

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

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

    return dp[-1] % mod

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

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

Solution (Python):
mod=1000000007

from itertools import accumulate, starmap
from operator import sub

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

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

n, k = map(int, input().split())
a = tuple(int(x) for x in input().split())

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


for pind, lim in enumerate(a, 1):
    csum = [0]
    t = 0
    for cnt in range(k + 1):
        t += d[pind - 1][cnt]
        csum.append(t)
    for distributed in range(k + 1):
        d[pind][distributed] = (csum[distributed + 1] - csum[max(0, distributed - lim)]) % mod

print(d[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][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)

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

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

cum = [0]*(K+2)

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

ans = dp[N][K]

print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return


def D():
    return


def E():
    n = I()
    a = LIR(n)
    b = [1<<i for i in range(n+1)]
    dp = [0 for i in range(b[n])]
    dp[0] = 1
    for i in range(n):
        for k in range(b[n])[::-1]:
            for j in range(n):
                if a[i][j] and not b[j]&k:
                    dp[b[j]|k] += dp[k]
                    dp[b[j]|k] %= mod
    print(dp[-1])

def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

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

def comb(a,b):
      return fact[a]*inv[b]*inv[a-b]%mod
  
n,k = map(int, input().split())
a = list(map(int, input().split()))
fact = [1]
for i in range(n+k):
    fact.append(fact[-1]*(i+1)%mod)
inv = [1]*(n+k+1)
inv[n+k] = pow(fact[n+k],mod-2,mod)
for i in range(n+k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
f = [comb(i+n-1,n-1) for i in range(k+1)]
for i in a:
    for j in range(k-i)[::-1]:
        f[j+i+1] -= f[j]
        f[j+i+1] %= mod
print(f[k])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    return


def D():
    return


def E():
    n = I()
    a = LIR(n)
    b = [1<<i for i in range(n+1)]
    dp = [0 for i in range(b[n])]
    dp[0] = 1
    for i in range(n):
        for k in range(b[n])[::-1]:
            for j in range(n):
                if a[i][j] and not b[j]&k:
                    dp[b[j]|k] += dp[k]
                    dp[b[j]|k] %= mod
    print(dp[-1])

def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    C()

Solution (Python):
N, K = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10**9+7
dp = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dp[0][i] = 1
for i in range(1, N+1):
    for j in range(K+1):
        tmp = 0 if j-a[i-1]-1 < 0 else dp[i-1][j-a[i-1]-1]
        dp[i][j] += dp[i-1][j]-tmp
        dp[i][j] %= mod
    if i != N:
        for j in range(K):
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod
print(dp[N][K])

Solution (Python):
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
n,k=map(int,raw_input().split())
arr=map(int,raw_input().split())
arr = [0]+arr
mod=10**9+7
dp = [] 
for i in range(n+1):
	ok=[]
	for j in range(k+1):
		ok.append(0)
	dp.append(ok)	
dp[0][0]=1	
for i in range(1,n+1):
	xx=0
	for j in range(k+1):
		if(j-arr[i]-1>=0):
			xx = (xx+dp[i-1][j] - dp[i-1][j-arr[i]-1])%mod
		else:
			xx=(xx+dp[i-1][j])%mod
		dp[i][j] = (xx)%mod	
	
print (dp[n][k])%mod

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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


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

dp[0,0] = 1

for i, a in enumerate(A):
    
    dp[i+1] = dp[i]
    
    dp[i+1,a+1:] -= dp[i,:-(a+1)]
    
    
    dp[i+1] = dp[i+1].cumsum()
    dp[i+1] %= MOD

print(dp[N][K])

Solution (Python):


import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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


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

dp[0,0] = 1

for i, a in enumerate(A):
    
    dp[i+1] = dp[i]
    
    dp[i+1,a+1:] -= dp[i,:-(a+1)]
    
    
    np.cumsum(dp[i+1], out=dp[i+1])
    dp[i+1] %= MOD

print(dp[N][K])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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


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

dp[0][0] = 1

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

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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


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

dp[0][0] = 1

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

Solution (Python):
from numpy import*
n,k,*a=map(int,open(0).read().split())
b=int64([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=map(int,open(0).read().split())
b=int64([1]+[0]*k)
for i in a:
  b[i+1:]-=b[:~i].copy()
  b=cumsum(b)%(10**9+7)
print(b[k])

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

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