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 = 'k = 72\nkk = k // 4\nK = 1<<k\ndef nu(L, sl = -1):\n    if sl == -1: sl = slice(0,len(L))\n    return int("".join([hex(K+a)[3:] for a in L[sl][::-1]]), 16)\nst = lambda n: hex(n)[2:]\nli = lambda s, l, r: [int(a, 16) % P if len(a) else 0 for a in [s[-(i+1)*kk:-i*kk] for i in range(l, r)]]\n\ndef grow(d, v, h, start):\n    h += [0] * d\n    f = [(-1 if (i+d) % 2 else 1) * fainv[i] * fainv[d-i] % P * h[i] % P for i in range(d+1)]\n    nuf = nu(f)\n    a = d * inv[v] % P\n    t = [1] * (3*d+3)\n    for i in range(1, 3*d+3):\n        t[i] = t[i-1] * (a - d + i - 1) % P\n    ti = [1] * (3*d+3)\n    ti[-1] = pow(t[-1], P-2, P)\n    for i in range(1, 3*d+3)[::-1]:\n        ti[i-1] = ti[i] * (a - d + i - 1) % P\n    iv = [1] * (3*d+3)\n    for i in range(1, 3*d+3):\n        iv[i] = ti[i] * t[i-1] % P\n    ###\n    fg = li(st(nuf * nu(iv[1:2*d+2])), d, d * 2 + 1)\n    for i, (_fg, _ti) in enumerate(zip(fg, ti)):\n        h[i] = h[i] * (_fg * t[d+i+1] % P * _ti % P) % P\n    ###\n    fg1 = li(st(nuf * nu(inv[1:2*d+2])), d, d * 2 + 1)\n    fg2 = li(st(nuf * nu(iv[d+2:3*d+3])), d, d * 2 + 1)\n    fg1.pop()\n    for i, (_fg1, _fg2) in enumerate(zip(fg1, fg2)):\n        h[i+d+1] = _fg1 * _fg2 % P * fa[d+i+1] % P * fainv[i] % P * t[2*d+i+2] % P * ti[d+i+1] % P\n    return h\n\ndef create_table(v, start = 1):\n    s = 1\n    X = [start, v + start]\n    while s < v:\n        X = grow(s, v, X, start)\n        s *= 2\n    table = [1]\n    for x in X:\n        table.append(table[-1] * x % P)\n    return table\n\nP = 10 ** 9 + 7\nnn = 4000000\nv = 1 << (nn.bit_length() + 1) // 2\nfa = [1] * (2*v+2)\nfainv = [1] * (2*v+2)\nfor i in range(2*v+1):\n    fa[i+1] = fa[i] * (i+1) % P\nfainv[-1] = pow(fa[-1], P-2, P)\nfor i in range(2*v+1)[::-1]:\n    fainv[i] = fainv[i+1] * (i+1) % P\ninv = [0] * (2*v+2)\nfor i in range(1, 2*v+2):\n    inv[i] = fainv[i] * fa[i-1] % P\n\ndef prod(a, b, vv): # a * (a + 1) * ... * (b - 1) % P\n    T = create_table(vv, a)\n    c = b - a\n    s = T[c//vv]\n    for i in range(c // vv * vv + a, b):\n        s = s * i % P\n    return s\n\ndef C(a, b):\n    if not 0 <= b <= a: return 0\n    if b * 2 > a: b = a - b\n    return prod(a - b + 1, a + 1, v) * pow(prod(1, b + 1, v), P - 2, P) % P\n\nN, M = map(int, input().split())\ns = sum([int(a) for a in input().split()])\nprint(C(N + M, s + N))'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 1264829