1257: #2000. 「SDOI2017」数字表格
[Creator : ]
Description
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 只想知道乘积对 1,000,000,007 取模后的结果。
$\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 只想知道乘积对 1,000,000,007 取模后的结果。
Input
有多组测试数据。
第一行一个数 T，表示数据组数。
接下来 T 行，每行两个数 n 和 m。
第一行一个数 T，表示数据组数。
接下来 T 行，每行两个数 n 和 m。
Output
输出 T 行，第 i 行的数是第 i 组数据的结果。
Constraints
对于 $10\%$ 的数据，$1 \leq n, m \leq 100$；
对于 $30\%$ 的数据，$1 \leq n, m \leq 1,000$；
另外存在 $30\%$ 的数据，$T \leq 3$；
对于 $100\%$ 的数据，$1 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1,000$。
对于 $30\%$ 的数据，$1 \leq n, m \leq 1,000$；
另外存在 $30\%$ 的数据，$T \leq 3$；
对于 $100\%$ 的数据，$1 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1,000$。
Sample 1 Input
3
2 3
4 5
6 7
Sample 1 Output
1
6
960