Description

Doris used her teacher’s supercomputer to generate an $n \times m$ table.

The number in the $i$-th row and the $j$-th column is $f_{\gcd(i,j)}$, where $\gcd(i,j)$ denotes the greatest common divisor of $i$ and $j$.

There are $n \times m$ numbers in total in Doris’s table. She wants to know the product of all these numbers.

Output the answer modulo $10^9+7$.

Input Format

There are multiple test cases in a single test file.

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines contains two integers $n, m$, describing one test case.

Output Format

For each test case, output one integer on a separate line representing the answer.

3
2 3
4 5
6 7

1
6
960

Hint

Constraints:

• For $10\%$ of the testdata, $n, m \leq 10^2$.
• For $30\%$ of the testdata, $n, m \leq 10^3$.
• For another $30\%$ of the testdata, $T \leq 3$.
• For $100\%$ of the testdata, $1 \leq T \leq 10^3$, $1 \leq n, m \leq 10^6$.

Translated by ChatGPT 5