题目背景

前情提要：调和级数求和。←注意，解决这道题目对于解决本题可能并不会有什么帮助。

题目描述

给定正整数 $n,p,k$。定义 $\operatorname{inv}(x,p^k)$ 是满足 $ax\equiv 1\pmod{p^k}$ 的小于 $p^k$ 的非负整数 $a$，如果不存在这样的 $a$ 则 $\operatorname{inv}(x,p^k)=0$。可以证明，如果存在这样的 $a$，那么它是唯一的。

现在，你需要求出下式的值：

由于答案可能很大，所以需要对 $p^k$ 取模。

注意此处 $\bm p$ 不一定是质数。

输入格式

一行三个正整数 $n,p,k$。

输出格式

一行一个正整数，表示欲求式子的值。答案对 $p^k$ 取模。

4 3 1

1

123456 78 9

37527411787678151

142857142857142857 2 59

573170602055236649

提示

本题采用捆绑测试。

• Subtask 1 (10pts)：$k=1$。
• Subtask 2 (40pts)：$\frac np\le 10^4$。
• Subtask 3 (50pts)：无特殊限制。

对于全部数据，有 $1\le n\le 10^{18}$，$2\le p\le 10^6$，$p^k\le 10^{18}$。