This year's autumn downpour has completely ruined the paint on Mr. Potyczek's fence. The fence must be covered as soon as possible with a special blue woodstain so that the coming winter does not ruin it irreversibly. Mr. Potyczek asked his neighbor's hardworking son, Bajtek, to do it. The boy completed the task this morning, but he did it quite carelessly because he was in a hurry to get to the next round of the Algorithmic Battles.

Mr. Potyczek's fence consists of $n$ pickets, and each picket is divided into $m$ segments of equal length. Bajtek painted each picket from top to bottom only once, which unfortunately might not have been enough to paint it entirely. Nevertheless, on each picket, a contiguous interval of segments was painted, and each segment was either completely painted or not painted at all. It also turned out that the part of the fence painted by the boy is connected, i.e., for any two consecutive pickets, the intervals of segments painted on them have a non-empty intersection.

For example, a painted fence might look like this:

However, the situation below is impossible for three different reasons:

• Picket number 1 was not painted at all.
• On picket number 3, a contiguous fragment was not painted.
• The intervals of segments painted on pickets 5 and 6 are disjoint.

Write a program that calculates how many different ways Bajtek could have painted the fence according to the above rules. Two ways are considered different if there exists a picket segment painted in one of them and not painted in the other. The number of ways can be quite large, so it is sufficient to provide the remainder when divided by a prime number $p$.

Input

The first and only line of input contains three positive integers $n$, $m$, and $p$ ($1 \le n \cdot m \le 10^7$, $10^8 \le p \le 10^9$, $p \in \mathbb{P}$), representing the number of pickets, the number of segments on each picket, and the prime number $p$, respectively.

Output

The output should contain a single integer representing the remainder when the number of different ways Bajtek could have painted the fence is divided by $p$.

Examples

Input 1

3 2 100000007

Output 1

17

Input 2

6 9 813443923

Output 2

57