CF2127F Hamed and AghaBalaSar

Hamid 为 a+b 问题写了 $3014$ 行代码，并将其中 $10$ 行给了 Hamed；然后 Hamed 想到了如下问题。 给定两个整数 $n$ 和 $m$。 一个数组 $a_1,a_2,\ldots,a_n$ 被称为“snake 数组”，当且仅当满足以下所有条件： - 数组 $a$ 的所有元素都是 $0$ 到 $m$ 之间的整数； - $a_1 + a_2 + \cdots + a_n = m$； - $a_n = \max\left([a_1, a_2, \ldots, a_n]\right)$。 我们定义 $f(a)$，其伪代码如下： ``` function f(array a): pos := 1 res := 0 令数组 nxt 使得 nxt[x] 是最小的下标 y 满足 y > x 且 a[y] > a[x]，不存在则未定义。 while pos < n: if a[pos] < a[n]: res += a[nxt[pos]] - a[pos] pos := nxt[pos] else: pos += 1 return res ``` 请计算所有 snake 数组 $a_1,a_2,\ldots,a_n$ 的 $f(a)$ 之和，结果对 $10^9+7$ 取模。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq m \leq 2 \cdot 10^5$）—— snake 数组的长度和所有元素之和。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示所有 snake 数组 $a_1,a_2,\ldots,a_n$ 的 $f(a)$ 之和，对 $10^9+7$ 取模。

在第一个测试用例中，有三个 snake 数组： - $f([0, 5]) = 5$； - $f([1, 4]) = 3$； - $f([2, 3]) = 1$。 因此，答案为 $5+3+1=9$。 在第二个测试用例中，有六个 snake 数组： - $f([0, 0, 4]) = 4$； - $f([0, 1, 3]) = 3$； - $f([1, 0, 3]) = 2$； - $f([1, 1, 2]) = 1$； - $f([0, 2, 2]) = 2$； - $f([2, 0, 2]) = 2$。 因此，答案为 $4+3+2+1+2+2=14$。 在第五个测试用例中，一个可能的 snake 数组为： - $f([3, 1, 4, 1, 5, 9]) = 6$。 由 ChatGPT 4.1 翻译