当 $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：
```cpp
#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;
}
```