题目名称 2657. [SDOI 2017] 数字表格
输入输出 product.in/out
难度等级 ★★★☆
时间限制 5000 ms (5 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-04-15
开放分组 全部用户
提交状态
分类标签
通过:2, 提交:3, 通过率:66.67%
GravatarYoungsc 100 14.084 s C++
关于 数字表格 的讨论

2657. [SDOI 2017] 数字表格

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

【题目描述】


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$组数据的结果

【样例输入】

3
2 3
4 5
6 7
  

【样例输出】

1
6
960