Summing Modular Inverses

Problem Statement:

Given positive integers \(n\), \(p\), and \(k\), let \(m = p^k\). Define the modular inverse \(\operatorname{inv}(x, p^k)\) as the unique non-negative integer \(a < p^k\) satisfying \[ a x \equiv 1 \pmod{p^k}, \] if such an \(a\) exists, and \(\operatorname{inv}(x, p^k)=0\) otherwise. It can be proven that if the inverse exists, it is unique.

Your task is to compute the sum \[ S = \sum_{i=1}^{n} \operatorname{inv}(i, p^k), \] and output \(S \bmod p^k\).
Note: \(p\) is not necessarily a prime.

inputFormat

The input consists of a single line containing three integers (n), (p), and (k), separated by spaces.

outputFormat

Output a single integer, which is the value of (\sum_{i=1}^{n} \operatorname{inv}(i, p^k) \bmod p^k).

sample

5 2 3

1