Part 0

由 $h_i=i \times s_i$，可以发现 $W=h_1\times h_2\times \ldots\times h_n=1 \times s_1 \times 2 \times s_2 \times \ldots \times n \times s_n=(1 \times 2 \times \ldots \times n) \times (s_1\times s_2\times \ldots\times s_n)=n! \times (s_1\times s_2\times \ldots\times s_n)$。

由于 $n \le 10^7$，阶乘部分可以预处理。下面只讨论如何求 $s_1\times s_2\times \ldots\times s_n$。

Part 1

先来模拟一下样例第 $4$ 组数据：

$\color{blue}i$	$\color{blue}1$	$\color{blue}2$	$\color{blue}3$	$\color{blue}4$	$\color{blue}5$	$\color{blue}6$	$\color{blue}7$	$\color{blue}8$	$\color{blue}9$	$\color{blue}10$
$s_i$	$6$	$3$	$\color{red}2$
$h_i$		$6$		$8$	$10$	$12$	$14$	$16$	$18$	$20$

再来模拟一下样例第 $5$ 组数据：

$\color{blue}i$	$\color{blue}1$	$\color{blue}2$	$\color{blue}3$	$\color{blue}4$	$\color{blue}5$	$\color{blue}6$	$\color{blue}7$	$\color{blue}8$	$\color{blue}9$	$\color{blue}10$	$\color{blue}11$	$\color{blue}12$	$\color{blue}13$	$\color{blue}14$	$\color{blue}15$	$\color{blue}16$	$\color{blue}17$	$\color{blue}18$	$\color{blue}19$	$\color{blue}20$	$\color{blue}21$	$\color{blue}22$	$\color{blue}23$
$s_i$	$44$	$22$	$15$	$12$	$10$	$9$	$8$	$\color{red}7$
$h_i$		$44$	$45$	$48$	$50$	$54$	$56$		$63$	$70$	$77$	$84$	$91$	$98$	$105$	$112$	$119$	$126$	$133$	$140$	$147$	$154$	$161$

Part 2

不难发现，当 $s_i \le i$ 时，$s_i$ 便不再变化了。

证明：

若 $s_i \le i$，则：

$$h_i=i \times s_i$$ $$\dfrac{h_{i}}{i+1}=\dfrac{i \times s_i}{i+1}$$

---

$$s_i \le i$$ $$s_i-i-1 \le -1$$ $$s_i-i-1<0$$

---

$$s_i = \dfrac{i \times s_i + s_i}{i+1} > \dfrac{i \times s_i}{i+1}>\dfrac{i \times s_i+s_i-i-1}{i+1}=s_i-1 $$$$s_i>\dfrac{i \times s_i}{i+1}>s_i-1$$ $$s_i>\dfrac{h_{i}}{i+1}>s_i-1$$ $$\lceil \dfrac{h_{i}}{i+1} \rceil=s_i$$ $$s_{i+1}=s_i$$

故 $s_i$ 不再变化。

Part 3

此外，当这个时刻到来时，$i \le \sqrt{2a}$。

证明：

$s_i \le i$ 等价于 $h_i \le i^2$。设 $f(i)=h_i$，$g(i)=i^2$，$d(i)=f(i)-g(i)$，则 $f(1)=a$，$g(1)=1$，$d(1)=a-1$，$s_i \le i$ 等价于 $d(i)\le0$；

当 $i$ 增加 $1$（即设 $j=i+1$）时，$g(j)-g(i)=2j-1$；

显然：

$$\lceil \dfrac{h_{i}}{j} \rceil-\dfrac{h_{i}}{j}<1$$ $$\lceil \dfrac{h_{j-1}}{j} \rceil \times j-\dfrac{h_{i}}{j} \times j<j $$$$h_j-h_i<j$$ $$f(j)-f(i)<j$$ $$f(j)-f(i)\le j-1$$

故 $d(j)-d(i)=[f(j)-g(j)]-[f(i)-g(i)]=[f(j)-f(i)]-[g(j)-g(i)]\le (j-1)-(2j-1)=-j$，即 $d(j)-d(i)\le-j$。

也就是说，当 $i$ 增加到 $j=i+1$ 时，$d$ 函数的值至少减小 $j$；

当 $i=\sqrt{2a}$ 时，$d(i)=a-1-2-3-\ldots-\sqrt{2a}=a-\dfrac{(1+\sqrt{2a})\times \sqrt{2a}}{2}=-\sqrt{\dfrac{a}{2}}<0$，显然这个时刻已经到来。

Part 4

于是，我们暴力计算 $s_1 \sim s_{\sqrt{2a}}$，剩下的上快速幂就行了。

最终的时间复杂度为 $O(n+T\sqrt{a})$，空间复杂度为 $O(n)$。

提示：代码中 $\lfloor\dfrac{(a+1)\times (i-1)}{i}\rfloor=\lfloor\dfrac{a\times (i-1)+(i-1)}{i}\rfloor=\lceil\dfrac{a\times (i-1)}{i}\rceil$。

Part 5

std：

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, N = 1e7 + 12, Real_N = 1e7;
int power(int a, int b, int p)
{
    if (b == 1) return a;
    int x = power(a, b >> 1, p);
    x = 1ll * x * x % p;
    if (b & 1) x = 1ll * x * a % p;
    return x;
}
int fc[N];
void preset()
{
    fc[0] = 1;
    for (int i = 1; i <= Real_N; i++)
        fc[i] = 1ll * fc[i - 1] * i % P;
}
int main()
{
    preset();
	int T;
    cin >> T;
    while (T--)
    {
        int n, a, i;
        cin >> n >> a;
        long long W = a;
	    for (i = 2; i <= n; i++)
	    {
		    a = (a + 1) * (i - 1) / i;
		    W *= a, W %= P;
		    if (a <= i) break;
	    }
	    if (i < n) W *= power(a, n - i, P), W %= P;
	    cout << W * fc[n] % P << endl;
    }
	return 0;
}