#2000. 「SDOI2017」数字表格

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入

3
2 3
4 5
6 7

样例输出

1
6
960

数据范围与提示

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