#2000. 「SDOI2017」数字表格

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

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

样例

样例输入

3
2 3
4 5
6 7

样例输出

1
6
960

数据范围与提示

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