[AdditionalFile2000.zip](file://AdditionalFile2000.zip?type=additional_file)

#2000. 「SDOI2017」数字表格

标签: 传统 | 时间限制: 5000 ms | 内存限制: 256 MiB |

题目描述

Doris 刚刚学习了 fibonacci 数列，用 $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$。