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