8816: BZOJ4816：[Sdoi2017]数字表格
Memory Limit：128 MB
Time Limit：5 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么 f[0]=0 f[1]=1 f[n]=f[n-1]+f[n-2],n>=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<=1000,1<=n,m<=10^6输出格式
输出T行，第i行的数是第i组数据的结果
样例输入
3 2 3 4 5 6 7
样例输出
1 6 960
提示
没有写明提示
题目来源
鸣谢infinityedge上传