题目名称	2657. [SDOI 2017] 数字表格
输入输出	`product.in/out`
难度等级	★★★★
时间限制	5000 ms (5 s)
内存限制	256 MiB
测试数据	10
题目来源	AAAAAAAAAA 于2018-04-15加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：5，提交：7，通过率：71.43%
神利·代目	100	4.204 s	51.14 MiB	C++
AAAAAAAAAA	100	6.070 s	62.33 MiB	C++
梦那边的美好ET	100	13.447 s	38.46 MiB	C++
Youngsc	100	14.084 s	31.79 MiB	C++
...	100	15.829 s	41.30 MiB	C++
Narcissus	30	35.688 s	39.41 MiB	C++
AAAAAAAAAA	30	35.779 s	62.33 MiB	C++

关于数字表格的近10条评论(全部评论)

2657. [SDOI 2017] 数字表格

★★★★ 输入文件：product.in 输出文件：product.out 简单对比
时间限制：5 s 内存限制：256 MiB

【题目描述】

Doris刚刚学习了$fibonacci$数列。用$f[i]$表示数列的第$i$项，那么

$$\begin{align}f[0]&=0\\f[1]&=1\\f[n]&=f[n-1]+f[n-2],n>=2\end{align}$$

Doris用老师的超级计算机生成了一个$n\times m$的表格，第$i$行第$j$列的格子中的数是$f[\mathrm{gcd}(i,j)]$，其中$\mathrm{gcd}(i,j)$表示$i$,$j$的最大公约数。Doris的表格中共有$n\times m$个数，她想知道这些数的乘积是多少。答案对$10^9+7$取模。

【输入格式】

有多组测试数据。第一个一个数$T$，表示数据组数。

接下来$T$行，每行两个数$n,m$

$T \leq 1000$,$1 \leq n$,$m \leq 10^6$

【输出格式】

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

【样例输入】

【样例输出】

1
6
960