P3704 [SDOI2017] Number Table

Doris just learned the Fibonacci sequence. Let $f_i$ denote the $i$-th term of the sequence, then $$f_0=0,f_1=1$$ $$f_n=f_{n-1}+f_{n-2},n\geq 2$$

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$.

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.

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

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