F. Hamed and AghaBalaSartime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output 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 resFind the sum of $$$f(a)$$$ over all snake arrays $$$a_1,a_2,\ldots,a_n$$$, modulo $$$10^9+7$$$.InputEach 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$$$. OutputFor 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$$$.ExampleInput82 53 44 65 106 23100 100142857 33333200000 0Output9 14 76 985 142112 771227753 865580631 0 NoteIn 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$$$.