题目描述

给定两个正整数 $n,a$。

现有两个正整数数列 $\{h_n\},\{s_n\}$ 和一个正整数 $W$，满足：

$$\begin{cases} s_1=a, \\ s_i=\lceil \dfrac{h_{i-1}}{i} \rceil, \\ h_i=i \times s_i,\\ W=h_1\times h_2\times \ldots\times h_n. \end{cases} $$

试计算 $W$ 的值。答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行，一个正整数 $T$，表示数据组数。

下面 $T$ 行，每行两个整数 $n,a$。

输出格式

$T$ 行，每行一个整数，对应一组数据的答案。

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

1
16
1080
721510288
57314155
568048964
118153594

提示

样例解释：

• 对于第 $1$ 组数据，$s$ 数列为 $\{1\}$，$h$ 数列为 $\{1\}$，故答案为 $1$。
• 对于第 $2$ 组数据，$s$ 数列为 $\{4,2\}$，$h$ 数列为 $\{4,4\}$，故答案为 $16$。
• 对于第 $3$ 组数据，$s$ 数列为 $\{9,5,4\}$，$h$ 数列为 $\{9,10,12\}$，故答案为 $1080$。
• 对于第 $4$ 组数据，取模前的答案为 $16721510400$。

---

测试点编号	$n \le$	$a \le$	分值
$1$	$100$	$1000$	$40$
$2$	$10^7$		$30$
$3$		$10^6$

对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^7$，$1 \le a \le 10^6$。