← 返回题目
题库练习 「SDOI2017」数字表格
← 上一题 下一题 →

A6785 | 「SDOI2017」数字表格

来源省选
时间限制5s
内存限制256MB
通过 / 提交0/0

题目描述

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

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

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
3
2 3
4 5
6 7
输出 #1
1
6
960
C++ 编辑器
输入
输出