Migrated from Lutece 3236 斐波那契数列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

斐波那契数列是这样定义的，设 $f_n$ 表示斐波那契数列的第 $n$ 项，则有：

波波王喜欢斐波那契数列，但是波波王觉得单纯求出斐波那契数列的某一项太无聊了，于是他决定变点花样。

波波王画了一个 $n\times m$ 大小的方格，行和列从 $1$ 开始标号，其中第 $i$ 行第 $j$ 列里面有数字 $f_{\gcd(i,j)}$ .

现在波波王想知道这 $n\times m$ 个格子里面的数的乘积是多少。

其中 $\gcd(i,j)$ 表示 $i$ 和 $j$ 的最大公因数。

由于答案可能会很大，因此答案需要对 $10^9+7$ 取模。

Input

输入的第一行是一个整数 $t$，表示测试数据的组数。

接下来 $t$ 行，每行两个整数 $n,m$ ，表示表格的大小。

Output

共 $t$ 行，一行一个整数表示答案。

Samples

3
2 3
4 5
6 7

1
6
960

Constraints

$1\leq t\leq10^3,1\leq n,m\leq 10^6$

Resources

2024 UESTC ICPC Training for Math