CF2127F Hamed and AghaBalaSar

Hamid wrote $3014$ lines of code for the a+b problem and gave $10$ lines of it to Hamed; then the following problem came to Hamed's mind. You are given two integers $n$ and $m$. An array $a_1,a_2,\ldots,a_n$ is called snake if and only if all of the following conditions hold: - All elements in $a$ are integers between $0$ and $m$; - $a_1 + a_2 + \cdots + a_n = m$; - $a_n=\max\left([a_1, a_2, \ldots, a_n]\right)$. We define $f(a)$ as in the following pseudocode: ``` function f(array a): pos := 1 res := 0 let nxt[x] be an array such that nxt[x] is the smallest index y such that y > x and a[y] > a[x], or undefined if no such y exists while pos < n: if a[pos] < a[n]: res += a[nxt[pos]] - a[pos] pos := nxt[pos] else: pos += 1 return res ``` Find the sum of $f(a)$ over all snake arrays $a_1,a_2,\ldots,a_n$, modulo $10^9+7$.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 2 \cdot 10^5$, $0 \leq m \leq 2 \cdot 10^5$) — the length of a snake array and the sum of all elements in a snake array. It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output a single integer — the sum of $f(a)$ over all snake arrays $a_1,a_2,\ldots,a_n$, modulo $10^9+7$.

In the first test case, there are three snake arrays: - $f([0, 5]) = 5$; - $f([1, 4]) = 3$; - $f([2, 3]) = 1$. Thus, the answer is $5+3+1=9$. In the second test case, there are six snake arrays: - $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$. Thus, the answer is $4+3+2+1+2+2=14$. In the fifth test case, a possible snake array is: - $f([3, 1, 4, 1, 5, 9]) = 6$.