Elementary Recurrence Computation

Fujisaki, known for his struggles with advanced mathematics courses, presents you with an elementary problem in basic mathematics. You are given the equation \(x + x^{-1} = k\), where \(k\) is an integer and \(k \ge 2\). Your task is to compute the value of \(x^n + x^{-n}\) for a given non-negative integer \(n\). It can be proven that for any integer \(n \ge 0\), the expression \(x^n + x^{-n}\) is an integer. Since the result might be very large, you only need to compute it modulo \(M\).

Hint: Notice that \(x^n + x^{-n}\) satisfies the recurrence relation:

[ f(0) = 2, \quad f(1) = k, \quad \text{and} \quad f(n) = k \cdot f(n-1) - f(n-2) \quad \text{for } n \ge 2. ]

inputFormat

The input consists of three space-separated integers: k, n, and M, where k (\(\ge 2\)) is the parameter from the equation, n (\(\ge 0\)) is the power for which you need to compute the expression, and M is the modulus.

outputFormat

Output a single integer: the value of \(x^n + x^{-n}\) modulo M.

sample

3 5 100

23