一径入繁华
题目背景
伴随龙年到来的，还有帆巨很喜欢的九省联考。为了爆踩压轴题。帆巨狠狠地重温了数论。
数论所生，繁华之地！
题目描述
帆巨觉得求 $x^a$ 在 $\bmod\ p$ 意义下的值太简单了，所以他想求 $\sigma_0^s(x^t)$ 在 $\bmod\ p$ 意义下的值。
帆帆不满足于只计算一次，于是他列了一个 $n\times n$ 的数表 $A$，保证第 $i$ 行第 $j$ 列（$1\le i,j\le n$）中的元素 $a_{i,j}$ 满足：
$$
a_{i,j}=\sum_{d\mid \gcd(i,j)}\mu\left(\dfrac{\gcd(i,j)}{d}\right)\times (\sigma_0(d^s))^t
$$
帆帆想知道这个数表长什么样子，但这个数表实在太大了，所以请你告诉他 $\det A$ 对 $10^9+7$ 取模后的结果。
注释：
1. 表达式中的各种函数含义在 **[这里](https://oi-wiki.org/math/number-theory/basic/#%E4%BE%8B%E5%AD%90)（$\mu$ 表示莫比乌斯函数，$\sigma_0$ 表示约数个数函数）**。
2. $\det A$ 表示方阵 $A$ 的 **[行列式](https://baike.baidu.com/item/%E8%A1%8C%E5%88%97%E5%BC%8F/2010180)**。
输入输出格式
输入格式
一行，输入三个整数 $n,s,t$。
输出格式
一行，输出一个整数表示答案。
输入输出样例
输入样例 #1
2 1 2输出样例 #1
2输入样例 #2
2 3 4输出样例 #2
254输入样例 #3
19 8 10输出样例 #3
913255725输入样例 #4
10000000000 1 2输出样例 #4
880793261说明
### 【样例 $1$ 解释】
矩阵 $A$ 如下：
$$
\begin{bmatrix}
1 & 1\\
1 &3
\end{bmatrix}
$$
行列式为 $1\times 3 - 1\times 1=2$。
### 【样例 $2$ 解释】
矩阵 $A$ 如下：
$$
\begin{bmatrix}
1 & 1\\
1 & 255
\end{bmatrix}
$$
行列式为 $1\times 255 - 1 \times 1=254$。
### 数据范围
本题采用 **子任务捆绑测试**。
对于 $100\%$ 的数据，保证 $1\le n\le 10^{11}$，$0\le s,t< 10^9+7$。
| 子任务编号 | $n$ | 特殊性质 | 分值 |
| :---------: | :-----------: | :-------: | :--: |
| Subtask #1 | $\le 500$ | 无 | $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$ | 无 | $10$ |
| Subtask #10 | $\le 10^{11}$ | 无 | $20$ |
**特殊性质** 一栏为空则表示没有特殊性质。子任务中没有规定范围的变量的值均在 $[0,10^9+7)$ 范围内生成。
时间限制：$\text{2000 ms}$；
空间限制：$\text{512 MB}$。