Fair Dice Throw

In the cafeteria there are \(n\) distinct dishes. Kluska has a \(k\)-faced die (when \(k=2\) it is a fair coin) and she wants to use it to select a dish such that every dish is chosen with equal probability.

To achieve fairness she devises the following strategy: she rolls the die \(x\) times in one round to generate an outcome in the range \(0\) to \(k^x-1\). If the outcome is less than \(T = \lfloor\frac{k^x}{n}\rfloor \cdot n\) then she outputs the dish number \(\text{(outcome mod }n)\). Otherwise, she discards the outcome and repeats the procedure. (Note that if \(k^x < n\) then no outcome is accepted.)

The expected number of dice rolls in one round is exactly \(x\); since the probability of a successful round is \(\frac{T}{k^x}=\frac{\lfloor k^x/n\rfloor\cdot n}{k^x}\), the overall expected number of dice rolls is

\[ E(x)=\frac{x\cdot k^x}{\lfloor k^x/n\rfloor \cdot n}. \]

Your task is to choose a fixed positive integer \(x\) (subject to \(k^x \ge n\)) that minimizes \(E(x)\) and output the corresponding minimum expected number of dice rolls modulo a given prime \(M\).

Note: When the answer is a rational number \(\frac{a}{b}\) in lowest terms, output \(a\cdot b^{-1}\) modulo \(M\), where \(b^{-1}\) is the modular inverse of \(b\) modulo \(M\).

inputFormat

The input consists of a single line with three integers \(n\), \(k\) and \(M\) (with \(2\le k\le n\) or possibly \(n\) not having all factors in \(k\)) where \(M\) is a prime number.

outputFormat

Output a single integer, which is the minimum expected number of dice rolls (as a rational number \(\frac{a}{b}\) reduced in lowest terms) modulo \(M\) i.e. \(a\cdot b^{-1}\bmod M\).

sample

2 2 1000000007

1