Counting Disliked Strings

Little Q hates palindromic strings in every form. He dislikes a string if either:

• It is a palindrome (reads the same forwards and backwards), for example, aa or aba.
• If by rotating the string – that is, by removing a prefix and appending it to the end – one obtains a palindrome, then the original string is also hated. For example, for aab one may remove the prefix a to obtain aba (a palindrome), so aab is disliked; similarly, baa is also hated.

More formally, consider a string \( s = a_0a_1\ldots a_{n-1} \) of length \( n \). For an integer \( r \) with \( 0 \le r < n \), denote by \[ R_r(s)=a_r a_{r+1}\ldots a_{n-1}a_0a_1\ldots a_{r-1} \] its cyclic rotation obtained by removing a prefix of length \( r \) and appending it to the end. The string \( s \) is considered "disliked" by Little Q if there exists an integer \( r \) such that \( R_r(s) \) is a palindrome, i.e. it satisfies \[ R_r(s)=\bigl(R_r(s)\bigr)^R \quad. \]

You are given three integers \( n \), \( k \) and \( p \). Consider all strings of length \( n \) made up from an alphabet of exactly \( k \) characters. Calculate the number of strings disliked by Little Q, and output the answer modulo \( p \).

Note: A string \( s = a_0a_1\ldots a_{n-1} \) is said to be a palindrome if \( a_i = a_{n-1-i} \) for all valid \( i \). In this problem, the rotation parameter \( r = 0 \) corresponds to the string itself.

Hint: It can be proved that for any string \( s \) the condition that there exists an \( r \) for which \( R_r(s) \) is a palindrome (i.e. \( s^R \) is a cyclic shift of \( s \)) is equivalent to a set of equations on the characters of \( s \). In particular, one may show that the answer can be expressed in closed‐form as follows:

• If \( n \) is odd, the answer is \[ n\cdot k^{\frac{n+1}{2}} - (n-1)\cdot k \pmod p, \]
• If \( n \) is even, the answer is \[ n\cdot k^{\frac{n}{2}} - (n-1)\cdot k \pmod p. \]

Your task is to implement this computation.

inputFormat

The input consists of a single line with three space‐separated integers:

• n: the length of the string (\( 1 \le n \le 10^9 \), for example),
• k: the number of characters in the alphabet (\( 1 \le k \le 10^9 \)),
• p: the modulus (a positive integer).

For example:

3 3 100

outputFormat

Output a single integer, the number of strings disliked by Little Q modulo p.

sample

1 3 100

3