描述

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

f[0]=0

f[1]=1

f[n]=f[n-1]+f[n-2], n>=2

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

样例输入1

3
2 3
4 5
6 7

样例输出1

1
6
960

限制

对于10％的数据，\(1\le n,m\le 100\)

对于30％的数据，\(1\le n,m\le 1000\)

另外存在30％的数据，\(T\le 3\)

对于100％的数据，\(T\le 1000,~1\le n,m\le 10^6\)

来源

SDOI 2017 Round1 Day1