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 = '# 考察:\n#  1,一見するとDPの問題。\n#    DP[m][i] = (B_1~B_iの総和がmとなるとき、i番目までを掛け算したものの和) とすればよさそう。\n#    しかし、Mの制約が大きい。上のDPはO(MN)かかるため、確実にTLEする。\n#  2,いろいろ考えたが、やはりMの制約が大きすぎる。もっと簡単な計算式があるのではないか。\n#  3,数え上げの問題として捉える。\n#    (B_i A_i)は、しきりをA_i個、ボールをK_i = (B_i-A_i)個並べる場合の数である。\n#    掛け算しているため、しきりA_i個、ボールK_i個のセクション(1~N)が独立して置かれているとみなせる。\n#    例：N = 3, A = [1,2,3], K = B-A = [6,5,3]のとき\n#     o o o | o o o (セクション1)\n#     o o | o | o o (セクション2)\n#     o | | o | o (セクション3)\n#    さらにB_iも可変。拘束条件は、今あるしきりとボールの合計がM個以下であることのみ。\n#    セクション1~Nを横並べにして、セクション間にさらにしきりを導入する。\n#    さらに最後のセクションの後にしきりを設ける。\n#    しきりとボールの合計がM個に満たない場合、この仕切りの後にその分のボールを置く。\n#    例：N = 3, A = [1,2,3], K = B-A = [6,5,3], M = 22(2個あまる)のとき\n#     o o o | o o o x o o | o | o o x o | | o | o x o o  (セクション間のしきりを「x」とした)\n#    ここで、2種類のしきりを区別する必要がない。\n#    (A_iが決まっているため、どの仕切りがどちらの意味のしきりであるかは一意に復元できる。)\n#  結論：しきりN+ΣA個、ボールM-ΣA個を並べる場合の数を求めればよい。\n\nN, M = map(int,input().split())\nA = list(map(int,input().split()))\nmod = 10**9 + 7\n\ninvs = [0,1]\n\nX = N + M # しきりとボールの数の和\nY = N + sum(A) # しきりの数\n\ndef inv(x):\n  if x == 1: return 1\n  else: return  (-invs[mod % x] * (mod // x)) % mod\nfor i in range(2,Y+1): #事前に逆元計算\n  invs.append(inv(i))\n  \nans = 1\nfor i in range(Y): #(X Y)の計算\n  ans *= (X-i) * invs[i+1]\n  ans %= mod\nprint(ans % mod)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13169