P12416 多项式高手

已知非负整数数列 $b_1,b_2,\cdots,b_n$ 的值，另有非负整数数列 $a$ 满足 $a_1+a_2+\cdots+a_n = m$，$a_1\le a_2\le\cdots\le a_n$。请求出对于所有满足条件的数列 $a$，$a_1b_1+a_2b_2+\cdots+a_nb_n$ 的和。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

第一行两个正整数 $n, m$。 第二行 $n$ 个整数 $b_1,b_2,\cdots,b_n$。

输出一行，表示所有 $a_1 b_1 + a_2 b_2 + \cdots + a_n b_n$ 的和对 $10^9+7$ 取模的结果。

### 样例解释 **【样例 1 解释】** 当且仅当 $a_1=6$ 时满足条件，所以答案为 $a_1\times b_1=6\times7=42$。 **【样例 2 解释】** 共有 $4$ 种可能的数列 $a$： - $a_1=0$，$a_2=6$ 时式子的值为 $0\times9+6\times7=42$； - $a_1=1$，$a_2=5$ 时式子的值为 $1\times9+5 \times7=44$； - $a_1=2$，$a_2=4$ 时式子的值为 $2\times9+4\times7=46$； - $a_1=3$，$a_2=3$ 时式子的值为 $3\times9+3\times7= 48$。 故答案为 $42+44+46+48=180$。 **【样例 3 解释】** 共有 $3$ 种可能的数列 $a$： - $a_1=0$，$a_2=0$，$a_3=3$ 时式子的值为 $0\times9+0\times5+3\times7=21$； - $a_1=0$，$a_2=1$，$a_3=2$ 时式子的值为 $0\times9+1\times5+2\times7=19$； - $a_1=1$，$a_2=1$，$a_3=1$ 时式子的值为 $1\times9+1\times5+1\times7=21$。 故答案为 $21+19+21=61$。 ### 大样例 **【样例 5】** 见选手目录下的 `mtt/mtt5.in` 与 `mtt/mtt5.out`。 这个样例满足测试点 $3$ 的约束条件。 **【样例 6】** 见选手目录下的 `mtt/mtt6.in` 与 `mtt/mtt6.out`。 这个样例满足测试点 $6$ 的约束条件。 **【样例 7】** 见选手目录下的 `mtt/mtt7.in` 与 `mtt/mtt7.out`。 这个样例满足测试点 $8$ 的约束条件。 **【样例 8】** 见选手目录下的 `mtt/mtt8.in` 与 `mtt/mtt8.out`。 这个样例满足测试点 $9$ 的约束条件。 ### 数据范围 空间限制 $512\text{MB}$。保证时空限制均为 $\text{std}$ 的 $2$ 倍以上。 对于所有数据，$1\le n\le10^5;~1\le m\le110,000;~n\le m\le n+10^4;~0\le b_i