[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×m$的表格, 第$i$行第$j$列的格子中的数是$f[\gcd(i,j)]$,其中$\gcd(i,j)$表示$i,j$的最大公约数。 Doris的表格中共有$n×m$个数,她想知道这些数的乘积是多少。 答案对$10^9+7$取模。

输入输出格式

输入格式


有多组测试数据。 第一个一个数$T$,表示数据组数。 接下来$T$行,每行两个数$n,m$

输出格式


输出$T$行,第$i$行的数是第$i$组数据的结果

输入输出样例

输入样例 #1

3
2 3
4 5
6 7

输出样例 #1

1
6
960

说明

对$10\%$的数据,$1\leq n,m\leq 100$ 对$30\%$的数据,$1\leq n,m\leq 1000$ 另外存在$30\%$的数据,$T\leq 3$ 对$100\%$的数据,$T\leq1000,1\leq n,m\leq 10^6$ 时间限制:5s 内存限制:128MB