#P4816. [Sdoi2017]数字表格

    ID: 3731 传统题 3000ms 128MiB 尝试: 1783 已通过: 733 难度: 7 上传者: 标签>CF2300提高+/省选-莫比乌斯反演线性筛倍数枚举批量求逆模逆元整除分块快速幂

[Sdoi2017]数字表格

题目背景

Doris 刚刚学习了 fibonacci 数列。用 fif_i 表示数列的第 ii 项,那么

f0=0,f1=1,fn=fn−1+fn−2(n≥2)f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}(n\ge 2)。

题目描述

Doris 用老师的超级计算机生成了一个 n×mn\times m 的表格,

第 ii 行第 jj 列的格子中的数是 fgcd⁡(i,j)f_{\gcd(i,j)},其中 gcd⁡(i,j)\gcd(i,j) 表示 i,ji,j 的最大公约数。

Doris 的表格中共有 n×mn\times m 个数,她想知道这些数的乘积是多少。

答案对 109+710^9+7 取模。

输入格式

本题单个测试点内有多组测试数据。

输入的第一行是一个整数 TT,表示测试数据的组数。

接下来 TT 行,每行两个整数 n,mn, m,表示一组数据。

输出格式

对于每组数据,输出一行一个整数表示答案。

样例输入

3
2 3
4 5
6 7

样例输出

1
6
960

数据范围与约定

  • 对于 10%10\% 的数据,保证 n,m≤102n,m\leq 10^2。
  • 对于 30%30\% 的数据,保证 n,m≤103n,m\leq 10^3。
  • 另有 30%30\% 的数据,保证 T≤3T\leq 3。
  • 对于 100%100\% 的数据,保证 1≤T≤1031 \leq T\leq 10^3,1≤n,m≤1061\leq n,m\leq 10^6。