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\nnu = lambda L: int("".join([hex(K+a)[3:] for a in L[::-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    ###\n    # g = [iv[i] for i in range(1, 2*d+2)]\n    g = iv[1:2*d+2]\n    fg = li(st(nuf * nu(g)), d, d * 2 + 1)\n    for i in range(d+1):\n        h[i] = h[i] * (fg[i] * t[d+i+1] % P * ti[i] % P) % P\n \n    ###\n    # g = [inv[i] for i in range(1, 2*d+2)]\n    g = inv[1:2*d+2]\n    fg = li(st(nuf * nu(g)), d, d * 2 + 1)\n    for i in range(d):\n        h[i+d+1] = fg[i] * fa[d+i+1] % P * fainv[i] % P\n \n    ###\n    # g = [iv[i] for i in range(d+2, 3*d+3)]\n    g = iv[d+2:3*d+3]\n    fg = li(st(nuf * nu(g)), d, d * 2 + 1)\n    for i in range(d):\n        h[i+d+1] = h[i+d+1] * (fg[i] * t[2*d+i+2] % P * ti[d+i+1] % P) % P\n \n    return h\n\n# Create a table of the factorial of the first v+2 multiples of v, i.e., [0!, v!, 2v!, ..., (v(v+1))!]\ndef create_table(v, start):\n    s = 1\n    X = [start, v + start]\n    while s < v:\n        X = grow(s, v, X, start)\n        s *= 2\n \n    table = [1]\n    for x in X:\n        table.append(table[-1] * x % P)\n    return table\n\ndef fact(i, table):\n    a = table[i//v]\n    for j in range(i//v*v+1, i+1):\n        a = a * j % P\n    return a\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, v): # a * (a + 1) * ... * (b - 1)\n    T = create_table(v, a)\n    c = b - a\n    s = T[c//v]\n    if c > 10:\n        vv = 1 << (c.bit_length() + 1) // 2\n        return s * prod(c // v * v + a, b, vv) % P\n    for i in range(c // v * v + a, b):\n        s = s * i % P\n    return s\n\ndef C(a, b):\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\nif 1:\n    N, M = list(map(int, input().split()))\n    A = [int(a) for a in input().split()]\n    s = sum(A)\n    print((C(N + M, s + N) if M >= s else 0))\n\n\n# print(prod(1, nn, v))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 1255927