CodeEff/ECCO huggingface dataset:
# Original solution
MAX_X = 10 ** 5 + 100

def main():
    N, M = [int(i) for i in input().split()]
    X = [0] * (MAX_X + 1)
    for i in map(int, input().split()):
        X[i] += 1
    Y = [sum(X[i::M]) for i in range(min(M, MAX_X))]
    # Mの倍数    
    ans = Y[0] // 2
    Y[0] = 0
    # M%2==0のM/2
    if M % 2 == 0:
        ans += Y[M//2] // 2
        Y[M//2] = 0    
    for i in range(1, M//2+1):
        j = M - i
        tmp = min(Y[i], Y[j])
        ans += tmp
        Y[i] -= tmp
        Y[j] -= tmp
    try:
        for i, n in enumerate(X):
            j = i % M
            if Y[j] < 2 or n < 2:
                continue
            tmp = min(Y[j]-Y[j]%2, n-n%2)
            ans += tmp // 2
            Y[j] -= tmp
    except IndexError:
        print((-1))
    print(ans)

if __name__ == "__main__":
    main()


# Optimized solution
MAX_X = 10 ** 5 + 100

def main():
    N, M = [int(i) for i in input().split()]
    X = [0] * (MAX_X + 1)
    for i in map(int, input().split()):
        X[i] += 1
    Y = [sum(X[i::M]) for i in range(min(M, MAX_X))]
    # Mの倍数    
    ans = Y[0] // 2
    Y[0] = 0
    # M%2==0のM/2
    try:
        if M % 2 == 0:
            ans += Y[M//2] // 2
            Y[M//2] = 0    
        for i in range(1, M//2+1):
            j = M - i
            tmp = min(Y[i], Y[j])
            ans += tmp
            Y[i] -= tmp
            Y[j] -= tmp
    except IndexError:
        print((-1))
    for i, n in enumerate(X):
        j = i % M
        if Y[j] < 2 or n < 2:
            continue
        tmp = min(Y[j]-Y[j]%2, n-n%2)
        ans += tmp // 2
        Y[j] -= tmp
    print(ans)

if __name__ == "__main__":
    main()
# Original solution
from collections import Counter
n,m=list(map(int,input().split()))
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+1*(m%2==1)):
  d=len(v[i])-len(v[m-i])
  if d<0:
    d=-d
    v[i],v[m-i]=v[m-i],v[i]
  c=sorted(list(Counter(v[i]).items()),key=lambda x:x[1])
  p=0
  for t in c:
    p+=(t[1]//2)
  a+=len(v[m-i])+min(p,(d//2))
a+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(a)

# Optimized solution
from collections import Counter
n,m=list(map(int,input().split()))
x=[int(i) for i in input().split()]
v=[[] for i in range(m)]
for i in x:v[i%m].append(i)
a=0
for i in range(1,m//2+1*(m%2==1)):
  x,y=v[i],v[m-i]
  d=len(x)-len(y)
  if d<0:
    d=-d
    x,y=y,x
  c=sorted(list(Counter(x).items()),key=lambda x:x[1])
  p=0
  for t in c:
    p+=(t[1]//2)
  a+=len(y)+min(p,(d//2))
a+=len(v[0])//2+(len(v[m//2])//2 if m%2==0 else 0)
print(a)
# Original solution
from collections import defaultdict, Counter
N, M = list(map(int, input().split()))
#X = list(map(int, input().split()))
C = Counter(list(map(int, input().split())))
D = defaultdict(int)
E = defaultdict(int)
for k, v in list(C.items()):
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

# Optimized solution
from collections import defaultdict, Counter
N, M = list(map(int, input().split()))
C = Counter(list(map(int, input().split())))
#D = defaultdict(int)
#E = defaultdict(int)
D = [0]*M
E = [0]*M
for k, v in list(C.items()):
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(eval(input()))
def getList():
    return list(map(int, input().split()))
import math

n, m = getList()
nums = getList()
n_mods = [0 for i in range(m)]
pair_mods = [0 for i in range(m)]
num_mods = [{} for i in range(m)]

for num in nums:
    modres = num % m
    n_mods[modres] += 1
    if num in num_mods[modres]:
        num_mods[modres][num] += 1
    else:
        num_mods[modres][num] = 1

    if num_mods[modres][num] % 2 == 0:
        pair_mods[modres] += 1

# print(n_mods)
# print(pair_mods)
ans = 0
for i in range(1, (m+1) // 2):
    left = i
    right = m - i
    ans += min(n_mods[left], n_mods[right])
    if n_mods[left] > n_mods[right]:
        ans += max(0, min(pair_mods[left], (n_mods[left] - n_mods[right]) // 2))
    else:
        ans += max(0, min(pair_mods[right], (n_mods[right] - n_mods[left]) // 2))
    # print(left, right, ans)

ans += n_mods[0] // 2
if m % 2 == 0:
    ans += n_mods[m//2] // 2

print(ans)

# Optimized solution
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(eval(input()))
def getNM():
    return list(map(int, input().split()))
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n,m = getlist()
    nums = getlist()

    cnt = Counter(nums)
    mod = [0 for i in range(m)]
    same = [0 for i in range(m)]

    for k, v in list(cnt.items()):
        mod[k%m] += v
        same[k%m] += v // 2

    ans = mod[0] // 2
    for i in range(1, int((m+2) // 2)):
        if i == m / 2:
            ans += mod[i] // 2
        else:
            other = m - i
            ans += min(mod[i], mod[other])
            if mod[i] > mod[other]:
                ans += min(same[i], (mod[i] - mod[other]) // 2)
            if mod[i] < mod[other]:
                ans += min(same[other], -(mod[i] - mod[other]) // 2)

    print(ans)

    # print(same, mod)

if __name__ == '__main__':
    main()

"""
9999
3

2916
"""
# Original solution
# 大混乱したので乱択

from random import randint
def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(eval(input()))
    if N==2:
        print((1))
        exit()
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        E[a].append(b)
        E[b].append(a)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d = dfs(u, v, root)
                res += d
                cnt_false += d == 0
        return res + max(0, cnt_false - 1)

    #for i in range(N):
    #    print(dfs(i, -1, i))

    print((max(dfs(i, -1, i) for i in sorted(list(range(N)), key=lambda x: -len(E[x]))[:5])))

main()


# Optimized solution
# 大混乱したので乱択  # これ嘘じゃないのか？？？

def main():
    import sys
    sys.setrecursionlimit(500000)
    N = int(eval(input()))
    if N==2:
        print((1))
        exit()
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = list(map(int, input().split()))
        E[a].append(b)
        E[b].append(a)

    def dfs(v=0, p=-1, root=0):
        cnt_child = 0
        cnt_false = 0
        res = 0
        for u in E[v]:
            if u!=p:
                cnt_child += 1
                d = dfs(u, v, root)
                res += d
                cnt_false += d == 0
        return res + max(0, cnt_false - 1)

    #for i in range(N):
    #    print(dfs(i, -1, i))

    print((max(dfs(i, -1, i) for i in sorted(list(range(N)), key=lambda x: -len(E[x]))[:1])))

main()
# Original solution
from itertools import accumulate

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

    def max2(x, y): return x if x >= y else y

    N, K = list(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[max2(0, j-A)]) % MOD for j in range(K+1)]

    print((dp[K]))


solve()


# Optimized solution
from itertools import accumulate

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

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

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

    print((dp[K]))


solve()
# Original solution
N, K = list(map(int, input().split()))
a = tuple(map(int, input().split()))

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


# Optimized solution
N, K = list(map(int, input().split()))
a = tuple(map(int, input().split()))

def main():
    l = [0] * (K+1)
    for i in range(N):
        t = 0
        lt = l
        l = [0] * (K + 1)
        for j in range(K+1):
            if i == 0:
                if a[i] >= j:
                    l[j] = 1
            elif j == 0:
                t = 1
                l[j] = 1
            else:
                if j <= a[i]:
                    t += lt[j]
                else:
                    t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print((main()))
# Original solution
N, K = list(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= [1 if a[0] >= j else 0 for j in range(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()))


# Optimized solution
N, K = list(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()))
# Original solution
# coding: utf-8

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:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        dp = list(accum(dp, lambda x, y: (x + y) % mod))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
    return(dp[k])

n, k = list(map(int, input().split())) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print((f(n, k, a)))


# Optimized solution
# coding: utf-8

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:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        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 = list(map(int, input().split())) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print((f(n, k, a)))
# Original solution
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+1)]
for i in range(N+1):
    dp[i][0] = 1

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

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

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


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

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

dp[0] = 1

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

    for j in range(1, K+1):
        sj = max([0, j-a[i-1]])
        dp[j] = (sums[j+1]-sums[sj]+MOD) % MOD
print((dp[K]))
# Original solution
def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    for i, a in enumerate(a_s[:-1]):
        dp[i + 1][0] = s = dp[i][0]% md
        for j in range(1, a + 1):
            dp[i + 1][j] = s = (s + dp[i][j])% md
        for j in range(a + 1, k + 1):
            dp[i + 1][j] = s = (s + dp[i][j] - dp[i][j - a - 1])% md
    return sum(dp[-1][k - a_s[-1]:]) % md


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


# Optimized solution
def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi = dp[i]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = list(map(int, input().split()))
a_s = list(map(int, input().split()))
print((f(k, a_s)))
# Original solution
def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi1[0] = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = (dpi1[j - 1] + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = (dpi1[j - 1] + dpi[j] - dpi[j - a - 1]) % md
        dpi = dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


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


# Optimized solution
def f(k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for dpi1, a in zip(dp[1:],a_s[:-1]):
        dpi1[0] = s = dpi[0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi=dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = list(map(int, input().split()))
a_s = list(map(int, input().split()))
print((f(k, a_s)))
# Original solution
class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

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

bit = BIT(k + 1, mod=MOD)
bit.add(0, 1)

for ai in a:
    for i in range(k, 0, -1):
        if ai >= i:
            x = bit.sum(i)
        else:
            x = bit.sum(i) - bit.sum(i - ai)
        bit.add(i, x % MOD)
print((bit.sum(k + 1) - bit.sum(k)))


# Optimized solution
MOD = 10 ** 9 + 7
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

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

for ai in a:
    for i in range(k, -1, -1):
        dp[i] += (b[i] - b[i - min(ai, i)]) % MOD
        dp[i] %= MOD
    for i in range(1, k + 2):
        b[i] = (b[i - 1] + dp[i - 1]) % MOD
        b[i] %= MOD
print((dp[-1]))
# Original solution
import sys

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

def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  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)   
  print((dp[n][k]))
main()

# Optimized solution
import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=list(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))
    #print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi%mod for dpi in dp]
    #print(dp)
  print((dp[k]))
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  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)   
  print(dp[n][k])"""
main()
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

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

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


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

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

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(eval(input()))
def MAP(): return list(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[この子までの範囲で][飴を配る総数] = 場合の数
dp = [[0] * (K+1) for i in range(N+1)]
# 0番目まで(誰もいない)の範囲で0個配る場合の数は1通り
dp[0][0] = 1

for i in range(N):
    sm = [0] * (K+2)
    # 今回送るi行について累積和を取る
    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):
        # iが送る予定の長さに応じた区間和を取る
        dp[i+1][j] = sm[j+1] - sm[max(j-aN[i], 0)]
        dp[i+1][j] %= MOD
        # for k in range(aN[i]+1):
        #     dp[i+1][j+k] += dp[i][j]
print((dp[N][K]))


# Optimized solution
# -*- coding: utf-8 -*-

import sys
from functools import reduce

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(eval(input()))
def MAP(): return list(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[この子までの範囲で][飴を配る総数] = 場合の数
dp = [[0] * (K+1) for i in range(N+1)]
# 0番目まで(誰もいない)の範囲で0個配る場合の数は1通り
dp[0][0] = 1

for i in range(N):
    sm = [0] * (K+2)
    # 今回送るi行について累積和を取る
    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):
        # iが送る予定の長さに応じた区間和を取る
        dp[i+1][j] = sm[j+1] - sm[max(j-aN[i], 0)]
        dp[i+1][j] %= MOD
        # for k in range(aN[i]+1):
        #     dp[i+1][j+k] += dp[i][j]
print((dp[N][K]))
# Original solution
import sys

def solve():
    input = sys.stdin.readline
    N, K = list(map(int, input().split()))
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    DP = [[0 for j in range(K + 1)] for i in range(N)]
    for i in range(A[0] + 1): DP[0][i] = 1
    for i in range(1, N):
        cum = [0] * (K + 2)
        for j in range(1, K + 2):
            cum[j] = (cum[j-1] + DP[i-1][j-1]) % mod
        #print(cum)
        for j in range(K + 1):
            DP[i][j] = (cum[j + 1] - cum[max(0, j - A[i])]) % mod
    print((DP[N-1][K]))
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

# Optimized solution
import sys

def solve():
    input = sys.stdin.readline
    N, K = list(map(int, input().split()))
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    DP = [[0 for j in range(K + 1)] for i in range(N)]
    for i in range(A[0] + 1): DP[0][i] = 1
    cum = [0] * (K + 2)
    for i in range(1, N):
        for j in range(1, K + 2): cum[j] = (cum[j-1] + DP[i-1][j-1]) % mod
        for j in range(K + 1): DP[i][j] = (cum[j + 1] - cum[max(0, j - A[i])]) % mod
    print((DP[N-1][K]))

    return 0

if __name__ == "__main__":
    solve()
# Original solution
# -*- coding: utf-8 -*-
import sys

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

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

mod=10**9+7


for n in range(N):
	W=[0]		#WA:累積和
	L=dp[n]
	l=len(L)
	a=A[n]
	for j,x in enumerate(L):
		if j==0:	W.append(x)
		else:	W.append( W[-1]+x )

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

	dp[n+1]=T



try:
	print(dp[N][K]%mod)
except IndexError:
	print(0)

# Optimized solution
# -*- coding: utf-8 -*-
import sys

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


mod=10**9+7

T=[1]
for n in range(N):
	W=[0]		#WA:累積和
	L=T
	l=len(L)
	a=A[n]
	for j,x in enumerate(L):
		if j==0:	W.append(x)
		else:	W.append( W[-1]+x )

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


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