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 翻译