[SDOI2017]数字表格
题号：NC20391
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项，那么 f[0]=0 f[1]=1 f[n]=f[n-1]+f[n-2],n ≥ 2 
Doris用老师的超级计算机生成了一个n×m的表格，第i行第j列的格子中的数是f[gcd(i,j)]，其中gcd(i,j)表示i, j的最大公约数。
Doris的表格中共有n×m个数，她想知道这些数的乘积是多少。答案对10^9+7取模。

输入描述:

有多组测试数据。第一个一个数T，表示数据组数。
接下来T行，每行两个数n,m
T ≤ 1000,1 ≤ n,m ≤ 10^6

输出描述:

输出T行，第i行的数是第i组数据的结果
示例1

输入

复制 
3
2 3
4 5
6 7

输出

复制 
1
6
960

备注:

对于10%的数据，保证 。
对于30%的数据，保证 。
另有30%的数据，保证 。
对于100%的数据，保证 。