AT_arc110_d [ARC110D] Binomial Coefficient is Fun

[problemUrl]: https://atcoder.jp/contests/arc110/tasks/arc110_d 長さが $ N $ の非負整数列 $ A $ があります。 長さが $ N $ で、和が $ M $ 以下である任意の非負整数列 $ B $ について、$ \prod\ _{i\ =\ 1}\ ^N\ \dbinom{B_i}{A_i} $ の値を計算し、その総和を $ 10^9\ +\ 7 $ で割った余りを出力してください。 ここで $ \dbinom{B_i}{A_i} $ は、$ B_i $ 個のものの中から $ A_i $ 個のものを選ぶ場合の数（二項係数）であり、$ B_i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ \prod\ _{i\ =\ 1}\ ^N\ \dbinom{B_i}{A_i} $ の総和を $ 10^9\ +\ 7 $ で割った余りを出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \leq\ N\ \leq\ 2000 $ - $ 1\ \leq\ M\ \leq\ 10^9 $ - $ 0\ \leq\ A_i\ \leq\ 2000 $ ### Sample Explanation 1 $ \prod\ _{i\ =\ 1}\ ^N\ \dbinom{B_i}{A_i} $ が $ 1 $ 以上となるような数列 $ B $ の定め方は、以下の $ 4 $ 通りです。 - $ B\ =\ 1,\ 2,\ 1 $ とする。このとき $ \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 $ とする。このとき $ \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 $ とする。このとき $ \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 $ とする。このとき $ \prod\ _{i\ =\ 1}\ ^N\ \dbinom{B_i}{A_i}\ =\ \dbinom{1}{1}\ \times\ \dbinom{2}{2}\ \times\ \dbinom{2}{1}\ =\ 2 $ である よって答えは $ 1\ +\ 2\ +\ 3\ +\ 2\ =\ 8 $ です。