「FAOI-R3」移民计划 (C)

题目描述

给定两个正整数 $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$ 行,每行一个整数,对应一组数据的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

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$ | $1000$ | $30$ | | $3$ | $10^7$ | $10^6$ | $30$ | 对于 $100\%$ 的数据,$1 \le T \le 10^5$,$1 \le n \le 10^7$,$1 \le a \le 10^6$。