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):
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
C = 10**9+7

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





for i in range(1, N):
    for j in range(K+1):
        csum[i-1][j+1] = (csum[i-1][j]+dp[i-1][j]) % C
        l = max(0, j-A[i])
        dp[i][j] = (csum[i-1][j+1]-csum[i-1][l]) % C
print(dp[-1][-1])

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)]
sdp = [[0] * (K + 1) for i in range(N + 1)]

dp[0][0] = 1
for j in range(len(dp[0])):
  sdp[0][j] = 1
  
for i in range(1, N + 1):
  for j in range(K + 1):
    dp[i][j] = sdp[i - 1][j]
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] -= sdp[i - 1][j - A[i - 1] - 1]
    dp[i][j] %= DIV
  sdp[i][0] = dp[i][0]
  for j in range(1, K + 1):
    sdp[i][j] = sdp[i][j - 1] + dp[i][j]
    sdp[i][j] %= 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)]
dp[0][0] = 1
sdp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(len(sdp[0])):
  sdp[0][i] = 1

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

print(dp[N][K])

Solution (Python):





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

def mod(num):
    return num % MOD

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

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

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

print(dp[N][K])

Solution (Python):
from itertools import accumulate

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
DP = [0] * (K+2)
DP[0] = 1
for a in A:
    D = [0] * (K+2)
    for i, d in enumerate(DP):
        if d > 0:
            D[i] += d
            D[min(K+1, i + a + 1)] -= d
    for i in range(1, K+2):
        D[i] += D[i-1]
        D[i] %= mod
    DP = D
print(DP[K])

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

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

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

for i in range(1, k+2):
    for j in range(1, n+1):
        K = i-1
        if K < arr[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]-dp[0][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-arr[j-1]-1][j-1]
        
        dp[i][j] %= mod


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

Solution (Python):
import sys
from itertools import accumulate

def main():
  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[0]=1
  for a in A:
    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])
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  
  
  
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    
  print(dp[n][k])"""
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(1,n+1):
    accum=[0,dp[i-1][0]]
    for j in range(1,k+1):
        accum.append((dp[i-1][j]+accum[-1])%mod)
    for j in range(k+1):
        dp[i][j]+=(accum[j+1]-accum[max(j-a[i-1],0)]+mod)%mod
        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 j in range(k+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    r=[0]*(k+2)
    for j in range(1,k+2):
        r[j]=(r[j-1]+dp[i-1][j-1])%mod
    for j in range(k+1):
        dp[i][j]=(r[j+1]-r[max(0,j-a[i-1])])%mod
print(dp[n][k]%mod)

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)
N=10**9 + 7
n,k=sep()
ar=lis()
dp=[[0 for _ in range(k+5)] for _ in range(n+5)]
prev=[0]*(k+5)
for j in range(min(ar[0]+1,k+1)):
    dp[1][j]=1
prev[0]=1
for j in range(1,k+1):
    prev[j] = (prev[j - 1] + dp[1][j]) % N
for i in range(2,n+1):
    for j in range(0,k+1):
        if j-ar[i-1]>0:
            dp[i][j]=((dp[i][j]+prev[j]-prev[j-ar[i-1]-1])%N +N)%N
        else:
            dp[i][j]=(dp[i][j]+prev[j])%N
    prev[0]=dp[i][0]
    for j in range(1,k+1):
        prev[j]=(prev[j-1]+dp[i][j])%N





print(dp[n][k])

Solution (Python):


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase




from bisect import bisect_right as br
from bisect import bisect







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)







mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  


def out(var): sys.stdout.write(str(var))  


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)
N=10**9 + 7
n,k=sep()
ar=lis()
dp=[[0 for _ in range(k+5)] for _ in range(n+5)]
prev=[0]*(k+5)
for j in range(min(ar[0]+1,k+1)):
    dp[1][j]=1
prev[0]=1
for j in range(1,k+1):
    prev[j] = (prev[j - 1] + dp[1][j]) % N
for i in range(2,n+1):
    for j in range(0,k+1):
        if j-ar[i-1]>0:
            dp[i][j]=((dp[i][j]+prev[j]-prev[j-ar[i-1]-1])%N +N)%N
        else:
            dp[i][j]=(dp[i][j]+prev[j])%N
    prev[0]=dp[i][0]
    for j in range(1,k+1):
        prev[j]=(prev[j-1]+dp[i][j])%N





print(dp[n][k])

Solution (Python):
'''
問題を言い換えると
0<=bi<=ai for any iにおいて、sum_i bi = Kとなる通りの数を求めよ

dp[i,j] .. 通りの総数、総和がちょうどjになるとき、:iまでの子供を考慮したとき
dp[i+1,j]=sum_{k=0}^{a_{i}} dp[i,j-k]

これではTLEになりそうなので、累積和で高速に計算する必要がある
'''

import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7

N, K = ints()
A = ints()

from numba import njit


@njit('(i8,i8,i8[:])', cache=True)
def solve(N, K, A):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        
        total = 0
        for j in range(K + 1):
            
            total += dp[i, j]
            total %= MOD
            if j - A[i] - 1 >= 0:
                total -= dp[i, j - A[i] - 1]
            dp[i + 1, j] = total % MOD

    print(dp[N, K])


solve(N, K, A)

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

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

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

Solution (Python):
import numpy as np
from numba import njit

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

max_candies = np.array(list(map(int, input().split())), dtype='int64')

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit('i8(i8,i8,i8[:],i8[:,:])', cache=True)
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)

Solution (Python):
import numpy as np
from numba import njit

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

max_candies = np.array(list(map(int, input().split())))

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)

Solution (Python):
import numpy as np
from numba import njit

N,K=map(int,input().split())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

dp=np.full((N+1,K+1),0,dtype=np.int64)
c=np.full(K+2,0,dtype=np.int64)
MOD=10**9+7

@njit('i8(i8,i8,i8,i8[:,:],i8[:])', cache=True)
def main(N,K,MOD,dp,c):

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

    return dp[N][K]

print(main(N,K,MOD,dp,c))

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
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(lis[i]+1):
        sm+=dp[i][j]
        dp[i+1][j]=sm%mod
    for j in range(lis[i]+1,k+1):
        sm+=dp[i][j]
        sm-=dp[i][j-lis[i]-1]
        dp[i+1][j]=sm%mod
print(dp[-1][-1]%mod)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
N,K = IL()
A = IL()

res = [0 for j in range(K+1)]
res[K] = 1

for i in range(N):
  acc = ACC1(res)
  for k in range(K):
    res[k] = acc[min(k+A[i],K)+1]-acc[k]
    res[k] %= MOD
print(res[0])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
A = LI()
dp = [0] * (k + 2)
dp[1] = 1
for i in range(n):
    dp = list(accumulate(dp))
    ndp = [0] * (k + 2)
    for j in range(k + 1):
        ndp[j + 1] = dp[j + 1] - dp[max(j - A[i], 0)]
        ndp[j + 1] %= mod
    dp = ndp


print(dp[-1])

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

N, K = list(map(int, input().split()))
a = [0] + 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(1,N+1):
    s = list(itertools.accumulate(dp[i - 1]))
    for k in range(K+1):
        m = max(0, k-a[i])
        if m > 0:
            dp[i][k] = ((s[k] % mod) - (s[m-1] % mod)) % mod
        else:
            dp[i][k] = s[k] % mod

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

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def pprint(M):
	for row in M:
		print(row)
	print("~~~")

def main():
	MOD = 10**9 + 7
	n, k = rli()
	A = list(rli())
	dp = [[0 for __ in range(k+1)] for _ in range(n)]
	psums = [[0 for __ in range(k+1)] for _ in range(n)]
	for c in range(min(k+1, A[0] + 1)):
		dp[0][c] = 1
	psums[0][0] = dp[0][0]
	for c in range(1, k+1):
		psums[0][c] = dp[0][c] + psums[0][c-1]
		psums[0][c] %= MOD
	for r in range(1, n):
		for c in range(k+1):
			cutoff = c - A[r] - 1
			dp[r][c] = psums[r-1][c] - (psums[r-1][cutoff] if cutoff >= 0 else 0)
			dp[r][c] %= MOD
		psums[r][0] = dp[r][0]
		for c in range(1, k + 1):
			psums[r][c] = dp[r][c] + psums[r][c-1]
			psums[r][c] %= MOD
	print(dp[n-1][k] % MOD)
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def pprint(M):
	for row in M:
		print(row)
	print("~~~")

def main():
	MOD = 10**9 + 7
	n, k = rli()
	A = list(rli())
	P = [A[0]]
	for i in range(1, len(A)):
		P.append(P[-1] + A[i])
	dp = [[0 for __ in range(k+1)] for _ in range(n)]
	psums = [[0 for __ in range(k+1)] for _ in range(n)]
	for c in range(min(k+1, A[0] + 1)):
		dp[0][c] = 1
	psums[0][0] = dp[0][0]
	for c in range(1, k+1):
		psums[0][c] = dp[0][c] + psums[0][c-1]
		psums[0][c] %= MOD
	for r in range(1, n):
		for c in range(min(k + 1, P[r] + 1)):
			cutoff = c - A[r] - 1
			dp[r][c] = psums[r-1][c] - (psums[r-1][cutoff] if cutoff >= 0 else 0)
			dp[r][c] %= MOD
		psums[r][0] = dp[r][0]
		for c in range(1, k + 1):
			psums[r][c] = dp[r][c] + psums[r][c-1]
			psums[r][c] %= MOD
	print(dp[n-1][k] % MOD)
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
from sys import stdin
mod = 10**9+7
n,k = map(int,stdin.readline().split())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    lst = [0]
    for j in range(k+1):
        lst.append((lst[-1]+dp[i-1][j])%mod)
        dp[i][j] = (lst[j+1]-lst[max(0,j-arr[i-1])])%mod
print(dp[-1][-1])

Solution (Python):
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  dp = [[0]*(K+2) for _ in range(N+1)]
  dp[0] = [0]+[1]*(K+1)
  for n in range(1,N+1):
    for k in range(1,K+2):
      dp[n][k] = (dp[n-1][k]-dp[n-1][max(0,k-A[n-1]-1)]+dp[n][k-1])%mod
  ans = (dp[-1][-1]-dp[-1][-2])%mod
  return ans
print(solve())

Solution (Python):
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
dp[0][0]=1
acum=[1]*(k+2)
acum[0]=0
for i in range(n):
  tmp=[0]
  for j in range(k+1):
    dp[i+1][j]=acum[j+1]-acum[max(0,j-arr[i])]
    dp[i+1][j]%=mod
    tmp.append((tmp[-1]+dp[i+1][j])%mod)
  acum=tmp
print(dp[-1][k]%mod)

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, k = ns()
    a = na()

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

    print(dp[n][k])


if __name__ == '__main__':
    main()