Background

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.

Problem Description

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 ($\mu$ denotes the Möbius function, and $\sigma_0$ denotes the divisor-counting function).
2. $\det A$ denotes the determinant of the square matrix $A$.

Input Format

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

Output Format

One line with one integer representing the answer.

2 1 2

2

2 3 4

254

19 8 10

913255725

10000000000 1 2

880793261

Hint

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		$s=1$	$10$
Subtask #4	$\le 10^{11}$	$s=1,t=2$
Subtask #5		$s=1$
Subtask #6		$t=1$	$2$
Subtask #7	$\le 10^{7}$	$t\le 9$	$10$
Subtask #8	$\le 10^{11}$		$15$
Subtask #9	$\le 10^7$	None	$10$
Subtask #10	$\le 10^{11}$		$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