数字表格
测试数据来自 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
- 1945
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者