题目描述

已知非负整数数列 $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 6
7

42

2 6
9 7

180

3 3
9 5 7

61

6 6
250863180 814744283 795773454 638846422 603293402 952439325

162287374

提示

样例解释

【样例 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<10^9+7$。

测试点	$n=$	$m=$	时间限制
$1$	$2$	$6$	$1\text s$
$2$	$6$
$3$	$50$	$99$
$4$	$100$	$199$
$5$	$500$	$999$
$6$	$5000$	$5000$
$7$		$9999$
$8$	$10^5$	$10^5$	$3\text s$
$9$		$100100$
$10$		$110000$	$0.6\text s$

出题人员

Idea：不知名用户，Solution：Konata28 & 不知名用户，Code：Konata28 & Milmon & 不知名用户，Data：不知名用户，Check：Milmon & Konata28。

本题来源于 2024.10.22 CSP-S 模拟赛。因为原版题目模数是 $998244353$，所以原版英文名为 ntt。数据点范围配置和时空限制相对原版题目略有改动。