Background

With the arrival of the Dragon Year, Fan Ju also enjoys the Joint Nine Provinces Examination. To excel in the final question, Fan Ju revisits number theory with great enthusiasm.

Number theory leads to prosperous lands!

Problem Description

Fan Ju finds calculating $x^a$ modulo $p$ too simple, so he wants to compute $\sigma_0^s(x^t)$ modulo $p$.

Fan Ju is not satisfied with just one calculation, so he creates an $n \times n$ matrix $A$, ensuring that the element $a_{i,j}$ in the $i$-th row and $j$-th column ($1 \le i, j \le n$) satisfies:

$$ a_{i,j} = \sum_{d \mid \gcd(i,j)} \mu\left(\frac{\gcd(i,j)}{d}\right) \times (\sigma_0(d^s))^t $$

Fan Ju wants to know what this matrix looks like, but it is too large, so please tell him the result of $\det A$ modulo $10^9+7$.

Notes:

1. The meanings of various functions in the expression can be found here ($\mu$ represents the Möbius function, $\sigma_0$ represents the divisor count function).
2. $\det A$ denotes the determinant of matrix $A$.

Input Format

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

Output Format

One line containing an integer representing the answer.

Sample Input and Output

Sample Input #1

2 1 2

Sample Output #1

2

Sample Input #2

2 3 4

Sample Output #2

254

Sample Input #3

19 8 10

Sample Output #3

913255725

Sample Input #4

10000000000 1 2

Sample Output #4

880793261

Notes

Sample 1 Explanation

Matrix $A$ is as follows:

$$ \begin{bmatrix} 1 & 1 \\ 1 & 3 \end{bmatrix} $$

The determinant is $1 \times 3 - 1 \times 1 = 2$.

Sample 2 Explanation

Matrix $A$ is as follows:

$$ \begin{bmatrix} 1 & 1 \\ 1 & 255 \end{bmatrix} $$

The determinant is $1 \times 255 - 1 \times 1 = 254$.

Data Range

This problem uses subtask-based testing.

For $100\%$ of the data, it is guaranteed that $1 \le n \le 10^{11}$, $0 \le s, t < 10^9+7$.

The Special Properties column is empty if there are no special properties. The values of variables not specified in the subtasks are generated within the range $[0, 10^9+7)$.

Time Limit: $2000$ ms;

Space Limit: $512$ MB.

见题面 Input 部分

见题面 Output 部分