数字表格

数字表格

测试数据来自 system/2013

描述

Doris刚刚学习了Fibnacci数列,用f[i]表示数列的第i项目,那么,

f[0]=0

f[1]=1

f[n]=f[n-1]+f[n-2], n>=2

Doris用老师的超级计算机生成了一个\(n\times m\)的表格,第i行第j列的格子中的数字是f[gcd(i,j)],其中gcd(i,j)表示i与j的最大公约数。

Doris的表格中共有\(n\times m\)个数,她想知道这些数的乘积是多少。这些数的乘积实在是太大了,所以Doris只想知道乘积对1000000007取模后的结果。

格式

输入格式

有多组测试数据。

第一行一个数T,表示数据组数。

接下来T行,每行两个数n和m。

输出格式

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

样例1

样例输入1

3
2 3
4 5
6 7

样例输出1

1
6
960

限制

对于10%的数据,\(1\le n,m\le 100\)

对于30%的数据,\(1\le n,m\le 1000\)

另外存在30%的数据,\(T\le 3\)

对于100%的数据,\(T\le 1000,~1\le n,m\le 10^6\)

来源

SDOI 2017 Round1 Day1

信息

ID
1057
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者