[SDOI2017] 数字表格

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$，表示一组数据。

对于每组数据，输出一行一个整数表示答案。

3
2 3
4 5
6 7

1
6
960

#### 数据规模与约定 - 对于 $10\%$ 的数据，保证 $n,m\leq 10^2$。 - 对于 $30\%$ 的数据，保证 $n,m\leq 10^3$。 - 另有 $30\%$ 的数据，保证 $T\leq 3$。 - 对于 $100\%$ 的数据，保证 $1 \leq T\leq 10^3$，$1\leq n,m\leq 10^6$。