As a PhD student in programming languages, Kanan Kujou spends her days dealing with various programs (functions). Today, she encountered a concise and interesting problem, so she decided to turn it into a competition problem.

As is well known, given an integer $m$, there are $M=m^m$ functions that map $\{1, \dots, m\}$ to $\{1, \dots, m\}$. Kanan denotes these functions as $f_1, \dots, f_M$.

Kanan first chooses two integers $a$ and $b$ independently and uniformly at random from $[1, M]$, and then chooses $2n$ integers $x_1, \dots, x_n$ and $y_1, \dots, y_n$ independently and uniformly at random from $[1, m]$.

Now, Kanan wants to know the probability that $f_a(x_i) = f_b(y_i)$ for every $i \in [1, n]$, i.e., $\Pr[\wedge_{i=1}^n f_a(x_i)=f_b(y_i)]$.

Input

The first line contains three integers $n, m, P$ ($1 \leq n \leq 40, 1 \leq m \leq 10^8, 10^8 < P \leq 10^9$).

It is guaranteed that $P$ is a prime number.

Output

Output a single integer representing the probability modulo $P$.

Examples

Input 1

1 2 998244353

Output 1

499122177

Input 2

2 2 998244353

Output 2

686292993

Input 3

10 7 998244353

Output 3

59788847

Note

In the first two examples, the true values of the probabilities are $1/2$ and $5/16$, respectively.

Subtasks

Subtask 1 (6 points): $1 \leq n, m \leq 5$.

Subtask 2 (21 points): $1 \leq n, m \leq 30$.

Subtask 3 (32 points): $1 \leq n, m \leq 40$.

Subtask 4 (41 points): $1 \leq n \leq 40, 1 \leq m \leq 10^8$.