题目描述

$m$ 个相同的乒乓球分到 $n$ 个不同的盒子中，已知第 $i$ 个盒子最多能容纳 $a_i$ 个乒乓球。所有乒乓球要求必须分完，求分配方案数。

答案对 $1000000007$ 取模。

输入格式

输入共 $2$ 行。

第 $1$ 行 $2$ 个整数，$n,m$ ，表示盒子的数量和乒乓球数量。

第 $2$ 行 $n$ 个整数，$a_1,a_2,...,a_n$ ，用空格隔开，表示每个盒子最多可容纳乒乓球的数量。

输出格式

输出 $1$ 行 $1$ 个整数，表示分配方案数，答案对 $1000000007$ 取模。

样例输入输出

3 5
2 2 3

6

说明：$6$ 种方案分别是： $(0,2,3),(1,1,3),(1,2,2),(2,0,3),(2,1,2),(2,2,1)$ ，每种方案按盒子顺序给出数量。

2 21
10 10

0

3 100000
100000 100000 100000

149966

数据范围

• $30\%$ 的数据：$1\ \leq\ n\ \leq\ 100$，$0\ \leq\ m\ \leq\ 200$，$0\ \leq\ a_i\ \leq\ m$；
• $100\%$ 的数据：$1\ \leq\ n\ \leq\ 100$，$0\ \leq\ m\ \leq\ 10^5$，$0\ \leq\ a_i\ \leq\ m$。