「FAOI-R3」移民计划 (C)
题目背景
**提示:题目描述最后附有一份简洁题意。**
题外话:CCF 的 F 是 Federation,不是 Foundation。
------------
$2035$ 年 $10$ 月 $24$ 日,为了响应国家号召,促进区域 OI 水平均衡发展,时任 GZCF(**G**ui**z**hou **C**omputer **F**ederation,贵州省计算机协会)主任 [strcmp(下称「小 W」)](https://www.luogu.com.cn/user/551861) 和时任 CQCF(**C**hong**q**ing **C**omputer **F**ederation,重庆市计算机协会)主任 [CQYC_ZJYjoe(下称「小 Z」)](https://www.luogu.com.cn/user/592080) 达成秘密协议:从重庆市抽调一批 OIers 移民到贵州省,路费等由小 Z 承担,但小 W 需要安排好 TA 们的住所。
题目描述
根据小 Z 的要求,小 W 一共要盖 $n$ 座楼房。为了更符合重庆人的品味(?),这些楼房需要「错落有致」:具体来说,第 $i$ 座楼房的层高应为 $i$ 米,且楼高 $h_i=s_i \times i$ 米**单调不降**(即 $h_i \ge h_{i-1}$)。当然,每座楼房的楼层数 $s_i$ 应为**正整数**。
与此同时,小 W 已经找到了一座层高为 $1$,楼层数 $s_1=a$ 的烂尾楼($h_1=a$),并决定将它作为第 $1$ 座楼房。
为了避免小 Z 反悔,小 W 决定尽快完工,因此他这么盖楼:
- 在所有使得 $h_2 =2 \times s_2\ge h_1$ 的 $s_2$ 中,取最小值作为 $s_2$,即 $s_2=\lceil\dfrac{h_1}{2}\rceil$;
- 在所有使得 $h_3 =3 \times s_3\ge h_2$ 的 $s_3$ 中,取最小值作为 $s_3$,即 $s_3=\lceil\dfrac{h_2}{3}\rceil$;
- 在所有使得 $h_4 =4 \times s_4\ge h_3$ 的 $s_4$ 中,取最小值作为 $s_4$,即 $s_4=\lceil\dfrac{h_3}{4}\rceil$;
- ……
- 在所有使得 $h_i =i \times s_i\ge h_{i-1}$ 的 $s_i$ 中,取最小值作为 $s_i$,即 $s_i=\lceil\dfrac{h_{i-1}}{i}\rceil$;
- ……
- 在所有使得 $h_n =n \times s_n\ge h_{n-1}$ 的 $s_n$ 中,取最小值作为 $s_n$,即 $s_n=\lceil\dfrac{h_{n-1}}{n}\rceil$。
当然,小 W 最关注的并不是这个,而是另外一件事情——他前一天成功忽悠了 CCF 主席,双方达成协议:CCF 补贴给小 W $h_1\times h_2\times \ldots\times h_n$ 元钱。
他想知道:此时 CCF 会补贴给他多少元钱?**答案对 $10^9+7$ 取模。**
------------
给定两个正整数 $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$。