1260: #2000. 「SDOI2017」数字表格

Memory Limit:256 MB Time Limit:5.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Doris 刚刚学习了 fibnacci 数列,用 f[i] f[i] f[i] 表示数列的第 i i i 项,那么:

f[0]=0f[1]=1f[n]=f[n−1]+f[n−2],n≥2 \begin{aligned} f[0] &= 0 \\ f[1] &= 1 \\ f[n] &= f[n - 1] + f[n - 2], n \geq 2 \end{aligned} f[0]f[1]f[n]=0=1=f[n1]+f[n2],n2

Doris 用老师的超级计算机生成了一个 n×m n \times m n×m 的表格,第 i i i 行第 j j j 列的格子中的数是 f[gcd(i,j)] f[\gcd(i, j)] f[gcd(i,j)],其中 gcd(i,j) \gcd(i, j) gcd(i,j) 表示 i i ij j j 的最大公约数。

Doris 的表格中共有 n×m n \times m n×m 个数,她想知道这些数的乘积是多少。

这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 1000000007 1000000007 1000000007 取模后的结果。

输入格式

有多组测试数据。
第一行一个数 T T T,表示数据组数。
接下来 T T T 行,每行两个数 n n nm m m

输出格式

输出 T T T 行,第 i i i 行的数是第 i i i 组数据的结果。

样例

样例输入

3
2 3
4 5
6 7

样例输出

1
6
960

数据范围与提示

对于 10% 10\% 10% 的数据,1≤n,m≤100 1 \leq n, m \leq 100 1n,m100
对于 30% 30\% 30% 的数据,1≤n,m≤1000 1 \leq n, m \leq 1000 1n,m1000
另外存在 30% 30\% 30% 的数据,T≤3 T \leq 3 T3
对于 100% 100\% 100% 的数据,1≤n,m≤106,1≤T≤1000 1 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1000 1n,m106,1T1000