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

内存限制：256 MB 时间限制：5.000 S 提交：0 解决：0
评测方式：文本比较 命题人：

题目描述

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[n−1]+f[n−2],n≥2​​

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 i 与 j j j 的最大公约数。

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

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

输入格式

有多组测试数据。
第一行一个数 T T T，表示数据组数。
接下来 T T T 行，每行两个数 n n n 和 m 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 1≤n,m≤100；
对于 30% 30\% 30% 的数据，1≤n,m≤1000 1 \leq n, m \leq 1000 1≤n,m≤1000；
另外存在 30% 30\% 30% 的数据，T≤3 T \leq 3 T≤3；
对于 100% 100\% 100% 的数据，1≤n,m≤106,1≤T≤1000 1 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1000 1≤n,m≤10​6​​,1≤T≤1000。