P12390 调和级数求和 2

前情提要：[调和级数求和](https://www.luogu.com.cn/problem/P5702)。←注意，解决这道题目对于解决本题可能并不会有什么帮助。

给定正整数 $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$，那么它是唯一的。 现在，你需要求出下式的值： $$\sum_{i=1}^n\operatorname{inv}(i,p^k)$$ 由于答案可能很大，所以需要对 $p^k$ 取模。 **注意此处 $\bm p$ 不一定是质数。**

无

无

**本题采用捆绑测试。** - 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}$。