A93223.「SDOI2017」数字表格

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 $ 组数据的结果。

对于 $ 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 $。