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.
import sys
# import numpy as np
# from numba import njit, i8, void

MOD = 10**9 + 7

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
# A = np.array([int(x) for x in sys.stdin.readline().rstrip().split()], dtype=np.int64)
A = [int(x) for x in sys.stdin.readline().rstrip().split()]


# @njit(void(i8, i8, i8[:]), cache=True)
def solve(N, M, A):

    S = sum(A)

    num = 1
    don = 1

    for i in range(1, S + N + 1):
        num = num * (M + N - (i - 1)) % MOD
        don = don * i % MOD

    ans = num * pow(don, MOD - 2, MOD) % MOD

    # print(INV)

    print(ans)


solve(N, M, A)

import sys
# import numpy as np
# from numba import njit, i8, void

MOD = 10**9 + 7

N, M = list(map(int, sys.stdin.readline().rstrip().split()))
# A = np.array([int(x) for x in sys.stdin.readline().rstrip().split()], dtype=np.int64)
A = [int(x) for x in sys.stdin.readline().rstrip().split()]


# @njit(void(i8, i8, i8[:]), cache=True)
def solve(N, M, A):

    S = sum(A)

    num = 1
    don = 1

    for i in range(1, S + N + 1):
        num = num * (M + N - (i - 1)) % MOD
        don = don * i % MOD

    ans = num * pow(don, MOD - 2, MOD) % MOD

    # print(INV)

    print(ans)


solve(N, M, A)
