P10154 "FAOI-R3" Immigration Plan

Given two positive integers $n, a$. There are two sequences of positive integers $\{h_n\}$, $\{s_n\}$ and a positive integer $W$, satisfying: $$\begin{cases} s_1=a, \\ s_i=\left\lceil \dfrac{h_{i-1}}{i} \right\rceil, \\ h_i=i \times s_i,\\ W=h_1\times h_2\times \ldots\times h_n. \end{cases}$$ Compute the value of $W$. **Output the answer modulo $10^9+7$.**

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain two integers $n, a$.

Output $T$ lines, each containing one integer, the answer for the corresponding test case.

Sample explanation: - For the $1$-st test case, the sequence $s$ is $\{1\}$ and the sequence $h$ is $\{1\}$, so the answer is $1$. - For the $2$-nd test case, the sequence $s$ is $\{4,2\}$ and the sequence $h$ is $\{4,4\}$, so the answer is $16$. - For the $3$-rd test case, the sequence $s$ is $\{9,5,4\}$ and the sequence $h$ is $\{9,10,12\}$, so the answer is $1080$. - For the $4$-th test case, the answer before taking modulo is $16721510400$. ------------ Constraints: | Test Point ID | $n \le$ | $a \le$ | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $1000$ | $40$ | | $2$ | $10^7$ | $1000$ | $30$ | | $3$ | $10^7$ | $10^6$ | $30$ | For $100\%$ of the testdata, $1 \le T \le 10^5$, $1 \le n \le 10^7$, $1 \le a \le 10^6$. Translated by ChatGPT 5