数字表格 ### 题目描述 Doris 刚刚学习了 fibonacci 数列。用 $f_i$ 表示数列的第 $i$ 项，那么 $$f_0=0,f_1=1$$ $$f_n=f_{n-1}+f_{n-2},n\geq 2$$ Doris 用老师的超级计算机生成了一个 $n\times m$ 的表格， 第 $i$ 行第 $j$ 列的格子中的数是 $f_{\gcd(i,j)}$，其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数。 Doris 的表格中共有 $n\times m$ 个数，她想知道这些数的乘积是多少。 答案对 $10^9+7$ 取模。 ### 输入描述 **本题单个测试点内有多组测试数据**。 输入的第一行是一个整数 $T$，表示测试数据的组数。 接下来 $T$ 行，每行两个整数 $n, m$，表示一组数据。 其中，$1 \leq T\leq 10^3$，$1\leq n,m\leq 10^6$。 ### 输出描述 对于每组数据，输出一行一个整数表示答案。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 2 3 4 5 6 7 ``` >输出 ```txt 1 6 960 ```