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

输出格式


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

输入输出样例

输入样例 #1

3
2 3
4 5
6 7

输出样例 #1

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