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 itertools\nN, M, *A = [int(_) for _ in open(0).read().split()]\n\n\nclass Factorial:\n    def __init__(self, max_fact, mod):\n        #mod should be prime number\n        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)\n        f = [1] * (max_fact + 1)\n        for idx in range(2, max_fact + 1):\n            f[idx] = f[idx - 1] * idx\n            f[idx] %= mod\n        if mod > max_fact:\n            fi = [pow(f[-1], mod - 2, mod)]\n            for idx in range(max_fact, 0, -1):\n                fi += [fi[-1] * idx % mod]\n            fi = fi[::-1]\n        else:\n            fi = [pow(n, mod - 2, mod) for n in f]\n        self.mod = mod\n        self.f = f\n        self.fi = fi\n\n    def factorial(self, n):\n        return self.f[n]\n\n    def factorial_inverse(self, n):\n        return self.fi[n]\n\n    def combination(self, n, r):\n        f = self.f\n        fi = self.fi\n        mod = self.mod\n        if n < r:\n            return 0\n        elif n < len(f):\n            return f[n] * fi[r] * fi[n - r] % mod\n        elif n < 2 * r:\n            r = n - r\n        if r < len(f):\n            ret = fi[r]\n            for _ in range(r):\n                ret *= n\n                ret %= mod\n                n -= 1\n            return ret\n        else:\n            1 / 0\n\n    def permutation(self, n, r):\n        f = self.f\n        fi = self.fi\n        mod = self.mod\n        if n < len(f):\n            return f[n] * fi[n - r] % mod\n        elif r < len(f):\n            ret = 1\n            for _ in range(r):\n                ret *= n\n                ret %= mod\n                n -= 1\n            return ret\n        else:\n            1 / 0\n\n    def homogeneous_product(self, n, r):\n        f = self.f\n        fi = self.fi\n        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod\n\n\nsuma = sum(A)\nmax_fact = suma + N\nmod = 10**9 + 7\nfact_instance = Factorial(max_fact, mod)\ncomb = fact_instance.combination\n\nans = comb(M + N, suma + N)\nprint(ans)\n'''\nans = 0\nfor bs in itertools.product(range(M + 1), repeat=N):\n    f = 0\n    if sum(bs) > M:\n        continue\n    ans += list(\n        itertools.accumulate([comb(b, a) for a, b in zip(A, bs)],\n                             func=lambda x, y: x * y % mod))[-1]\n    ans %= mod\nprint(ans)\n'''\n'''\nans(N, M, sum(A))\n\nans(3, 1, 1) = C[4, 0]\nans(3, 2, 2) = C[5, 0]\nans(3, 3, 3) = C[6, 0]\n\nans(3, 4, 4) = C[7, 0]\n\nans(3, 6, 5) = C[9, 1]\nans(4, 6, 5) = C[10, 1]\n\nans(N, M, sum(A)) = C[N + M, M - sum(A)]\n'''\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18725