P10182 A Straight Path into Prosperity

 Along with the Year of the Dragon, there comes the nine-province joint mock exam that Fanju really likes. In order to completely crush the final problem, Fanju seriously reviewed number theory again. Where number theory is born, there lies a land of prosperity.

Fanju thinks computing the value of $x^a$ modulo $p$ is too easy, so he wants to compute the value of $\sigma_0^s(x^t)$ modulo $p$. Fanfan is not satisfied with computing it only once, so he wrote an $n\times n$ number table $A$, guaranteeing that the element $a_{i,j}$ in row $i$ and column $j$ ($1\le i,j\le n$) satisfies: $$ a_{i,j}=\sum_{d\mid \gcd(i,j)}\mu\left(\dfrac{\gcd(i,j)}{d}\right)\times (\sigma_0(d^s))^t $$ Fanfan wants to know what this number table looks like, but it is far too large. So please tell him the value of $\det A$ modulo $10^9+7$. Notes: 1. The meanings of the functions in the expression are explained **[here](https://oi-wiki.org/math/number-theory/basic/#%E4%BE%8B%E5%AD%90) ($\mu$ denotes the Möbius function, and $\sigma_0$ denotes the divisor-counting function)**. 2. $\det A$ denotes the **[determinant](https://baike.baidu.com/item/%E8%A1%8C%E5%88%97%E5%BC%8F/2010180)** of the square matrix $A$.

One line with three integers $n,s,t$.

One line with one integer representing the answer.

### Sample $1$ Explanation Matrix $A$ is: $$ \begin{bmatrix} 1 & 1\\ 1 &3 \end{bmatrix} $$ Its determinant is $1\times 3 - 1\times 1=2$. ### Sample $2$ Explanation Matrix $A$ is: $$ \begin{bmatrix} 1 & 1\\ 1 & 255 \end{bmatrix} $$ Its determinant is $1\times 255 - 1 \times 1=254$. ### Constraints This problem uses **bundled subtasks**. For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^{11}$, $0\le s,t< 10^9+7$. | Subtask ID | $n$ | Special Property | Score | | :---------: | :-----------: | :--------------: | :---: | | Subtask #1 | $\le 500$ | None | $8$ | | Subtask #2 | $\le 10^7$ | $s=1,t=2$ | $5$ | | Subtask #3 | $\le 10^7$ | $s=1$ | $10$ | | Subtask #4 | $\le 10^{11}$ | $s=1,t=2$ | $10$ | | Subtask #5 | $\le 10^{11}$ | $s=1$ | $10$ | | Subtask #6 | $\le 10^{11}$ | $t=1$ | $2$ | | Subtask #7 | $\le 10^{7}$ | $t\le 9$ | $10$ | | Subtask #8 | $\le 10^{11}$ | $t\le 9$ | $15$ | | Subtask #9 | $\le 10^7$ | None | $10$ | | Subtask #10 | $\le 10^{11}$ | None | $20$ | If the “Special Property” column is empty, it means there is no special property. For variables whose ranges are not specified in a subtask, their values are generated within $[0,10^9+7)$. Time limit: $\text{2000 ms}$. Memory limit: $\text{512 MB}$. Translated by ChatGPT 5