Bob has discovered a new interesting game. In this game, Bob has $n$ enemies to defeat, and each enemy has one of $m$ colors. In one turn, Bob can attack a contiguous segment of enemies, provided that all enemies in that segment have the same color.

Bob wants to attack as many enemies as possible in a single turn, but sometimes he is not satisfied. For any given configuration of colors, we define Bob's happiness as the maximum number of enemies he can attack in a single turn. Bob wants to know the sum of his happiness over all $m^n$ possible color configurations of the enemies. Since this number can be very large, you need to output the result modulo a given prime number.

Implementation Details

You should include coloring.h and implement the following procedure:

int totalhappy(int n, int m, int p)

• $n$: The number of enemies.
• $m$: The total number of colors.
• $p$: The modulus. A prime number.
• The procedure you implement will be called exactly once.
• You should return the sum of happiness over all coloring schemes modulo $p$: an integer in the range $[0, p-1]$.

Examples

Consider the call: totalhappy(2, 2, 998244353)

If the two enemies have the same color, Bob's happiness is $2$; otherwise, it is $1$. Therefore, the total happiness is $2+2+1+1=6$. A correct program should return $6 \bmod 998244353 = 6$.

Constraints

$1 \le n \le 10^6$

$1 \le m \le 10^9$

$10^8 < p < 10^9$, where $p$ is a prime number.

Subtasks

1. (10 points) $n \le 10$, $m \le 4$
2. (20 points) $n \le 100$
3. (30 points) $n \le 50000$
4. (20 points) $m \le 10^6$
5. (20 points) No additional constraints.

Sample Grader

The sample grader reads the input in the following format:

• One line: $n~m~p$

The sample grader prints your output in the following format:

• One line: your return value