P3704 [SDOI2017] 数字表格

Doris 刚刚学习了 fibonacci 数列。用 $f_i$ 表示数列的第 $i$ 项，那么 $$f_0=0,f_1=1$$ $$f_n=f_{n-1}+f_{n-2},n\geq 2$$

Doris 用老师的超级计算机生成了一个 $n\times m$ 的表格， 第 $i$ 行第 $j$ 列的格子中的数是 $f_{\gcd(i,j)}$，其中 $\gcd(i,j)$ 表示 $i,j$ 的最大公约数。 Doris 的表格中共有 $n\times m$ 个数，她想知道这些数的乘积是多少。 答案对 $10^9+7$ 取模。

无

无

#### 数据规模与约定 - 对于 $10\%$ 的数据，保证 $n,m\leq 10^2$。 - 对于 $30\%$ 的数据，保证 $n,m\leq 10^3$。 - 另有 $30\%$ 的数据，保证 $T\leq 3$。 - 对于 $100\%$ 的数据，保证 $1 \leq T\leq 10^3$，$1\leq n,m\leq 10^6$。