We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2000
 - 1 \leq M \leq 10^9
 - 0 \leq A_i \leq 2000

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_N

-----Output-----
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).

-----Sample Input-----
3 5
1 2 1

-----Sample Output-----
8

There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
 - B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;
 - B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;
 - B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;
 - B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "import sys\nfrom collections import deque\nfrom copy import deepcopy\nfrom bisect import bisect_left, bisect_right, insort_left, insort_right\nfrom heapq import heapify, heappop, heappush\nfrom itertools import product, permutations, combinations, combinations_with_replacement\nfrom functools import reduce\nfrom math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians\n\nsys.setrecursionlimit(10**6)\nINF = 10**20\neps = 1.0e-20\nMOD = 10**9+7\n\ndef lcm(x,y):\n    return x*y//gcd(x,y)\ndef lgcd(l):\n    return reduce(gcd,l)\ndef llcm(l):\n    return reduce(lcm,l)\ndef powmod(n,i,mod=MOD):\n    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)\ndef div2(x):\n    return x.bit_length()\ndef div10(x):\n    return len(str(x))-(x==0)\ndef intput():\n    return int(input())\ndef mint():\n    return map(int,input().split())\ndef lint():\n    return list(map(int,input().split()))\ndef ilint():\n    return int(input()), list(map(int,input().split()))\ndef judge(x, l=['Yes', 'No']):\n    print(l[0] if x else l[1])\ndef lprint(l, sep='\\n'):\n    for x in l:\n        print(x, end=sep)\ndef ston(c, c0='a'):\n    return ord(c)-ord(c0)\ndef ntos(x, c0='a'):\n    return chr(x+ord(c0))\nclass counter(dict):\n    def __init__(self, *args):\n        super().__init__(args)\n    def add(self,x,d=1):\n        self.setdefault(x,0)\n        self[x] += d\n    def list(self):\n        l = []\n        for k in self:\n            l.extend([k]*self[k])\n        return l\nclass comb():\n    def __init__(self, n, mod=None):\n        self.l = [1]\n        self.n = n\n        self.mod = mod\n    def get(self,k):\n        l,n,mod = self.l, self.n, self.mod\n        if k<0 or n<k:\n            return 0\n        k = n-k if k>n//2 else k\n        while len(l)<=k:\n            i = len(l)\n            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)\n        return l[k]\ndef pf(x,mode='counter'):\n    C = counter()\n    p = 2\n    while x>1:\n        k = 0\n        while x%p==0:\n            x //= p\n            k += 1\n        if k>0:\n            C.add(p,k)\n        p = p+2-(p==2) if p*p<x else x\n    if mode=='counter':\n        return C\n    S = set([1])\n    for k in C:\n        T = deepcopy(S)\n        for x in T:\n            for i in range(1,C[k]+1):\n                S.add(x*(k**i))\n    if mode=='set':\n        return S\n    if mode=='list':\n        return sorted(list(S))\n\n######################################################\n\ndef cmb(n, r, mod):\n    if ( r<0 or r>n ):\n        return 0\n    r = min(r, n-r)\n    return g1[n] * g2[r] * g2[n-r] % mod\n\nmod = 10**9+7 #出力の制限\nN = 10**4\ng1 = [1, 1] # 元テーブル\ng2 = [1, 1] #逆元テーブル\ninverse = [0, 1] #逆元テーブル計算用テーブル\n\nfor i in range( 2, N + 1 ):\n    g1.append( ( g1[-1] * i ) % mod )\n    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )\n    g2.append( (g2[-1] * inverse[-1]) % mod )\n\nN,M=mint()\nA=lint()\nS=sum(A)\nif S>M:\n    print(0)\n    return\n    \nn = S+N+M-S\nk = S+N\nmod = 10**9 + 7\n\n# def modinv(x):\n# xの逆元を求める際に[mod % x]の逆元が必要なので、関数の形でxの逆元を直接求めることは難しい。再帰を使えば行けそうだけど。\n\nmodinv_table = [-1] * (k+1)\nmodinv_table[1] = 1\nfor i in range(2, k+1):\n    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod\n\ndef binomial_coefficients(n, k):\n    ans = 1\n    for i in range(k):\n        ans *= n-i\n        ans *= modinv_table[i + 1]\n        ans %= mod\n    return ans\n\nprint(binomial_coefficients(n, k))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: