#649. #2000. 「SDOI2017」数字表格

#2000. 「SDOI2017」数字表格

题目描述

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

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

Doris 用老师的超级计算机生成了一个 n×mn \times m 的表格,第 ii 行第 jj 列的格子中的数是 f[gcd⁡(i,j)]f[\gcd(i, j)],其中 gcd⁡(i,j)\gcd(i, j) 表示 ii 与 jj 的最大公约数。 Doris 的表格中共有 n×mn \times m 个数,她想知道这些数的乘积是多少。 这些数的乘积实在是太大了,所以 Doris 只想知道乘积对 10000000071000000007 取模后的结果。

输入格式

有多组测试数据。
第一行一个数 TT,表示数据组数。
接下来 TT 行,每行两个数 nn 和 mm。

输出格式

输出 TT 行,第 ii 行的数是第 ii 组数据的结果。

3
2 3
4 5
6 7
1
6
960

数据范围与提示

对于 10%10\% 的数据,1≤n,m≤1001 \leq n, m \leq 100;
对于 30%30\% 的数据,1≤n,m≤10001 \leq n, m \leq 1000;
另外存在 30%30\% 的数据,T≤3T \leq 3;
对于 100%100\% 的数据,1≤n,m≤106,1≤T≤10001 \leq n, m \leq 10 ^ 6, 1 \leq T \leq 1000。