题目背景

伴随龙年到来的，还有帆巨很喜欢的九省联考。为了爆踩压轴题。帆巨狠狠地重温了数论。

数论所生，繁华之地！

题目描述

帆巨觉得求 $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. 表达式中的各种函数含义在 这里（$\mu$ 表示莫比乌斯函数，$\sigma_0$ 表示约数个数函数）。
2. $\det A$ 表示方阵 $A$ 的 行列式。

输入格式

一行，输入三个整数 $n,s,t$。

输出格式

一行，输出一个整数表示答案。

2 1 2

2

2 3 4

254

19 8 10

913255725

10000000000 1 2

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		$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$	无	$10$
Subtask #10	$\le 10^{11}$		$20$

特殊性质 一栏为空则表示没有特殊性质。子任务中没有规定范围的变量的值均在 $[0,10^9+7)$ 范围内生成。

时间限制：$\text{2000 ms}$；

空间限制：$\text{512 MB}$。