Problem Description

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$.

Input Format

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 Format

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

7
1 1
2 4
3 9
10 6
23 44
108 301
9181918 918918

1
16
1080
721510288
57314155
568048964
118153594

Hint

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$		$30$
$3$		$10^6$

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