Bug

　

You are designing the world's most powerful computer system, "Nayuta". However, during the implementation of the prototype of this system, you find a bug that causes the system to stop when the instruction sequence meets certain conditions.

The system works by giving an instruction string of length $N$ as a program. When the $m$-th instruction in the instruction sequence is represented by the number $X_m$, it is found that the condition for the bug to occur is that there exists a pattern of instructions in the instruction sequence such that $X_i + X_{j-1} = X_j + X_{i-1}$ for some integer $i,j$ ($2 \leq i＜j \leq N$).

To find out how much of an effect this bug has, you decided to find out how many instruction sequences of a certain length can cause the bug.

Write a program to find out how many instruction sequences of length $N$ will cause a failure. It is assumed that instructions can be represented by integers between 1 and $K$. The answer should be the remainder divided by the given prime number $M$.

Input

The input is given in the following form.

$N$ $K$ $M$

In a line, the length of the instruction sequence $N$ ($3 \leq N \leq 100,000$), the number of instruction types $K$ ($1 \leq K \leq 10$), and the prime number $M$ ($100,000,007 \leq M \leq 1,000,000,007$) are given.

Output

Outputs the remainder obtained by dividing the number of faulty instruction sequences by $M$.

Sample Input and Output

Sample Input 1

3 2 100000007

Sample Output 1

2

If we represent the instruction sequence as $(X_1,X_2,X_3)$, there are eight possible instruction sequences: $(1,1,1)$, $(1,1,2)$, $(1,2,1)$, $(1,2,2)$, $(2,1,1)$, $(2,1,2)$, $(2,1,2)$, $(2,2,1)$, and $(2,2,2)$. Of these, the instruction sequence in which the failure occurs is $(1,1,1)$ and $(2,2,2)$.

Sample Input 2

9 10 100000037

Sample Output 2

66631256

There are 866631552 instruction sequences that cause the bug, and the output is the remainder of the number divided by the prime number 100000037.

---