Background

$shik$ has gone into nuclear engineering.

Description

$127$ wants to test your ability to solve equations.

You are given the following equation: $AB \equiv A \pmod q$, where $q$ is a prime number, and $A, B$ are $n \times n$ matrices with elements $\in \{0, 1, 2, \dots, q-1\}$ (all subsequent matrices must also satisfy this).

Matrix congruence $S \equiv T \pmod p$ is defined as $\forall i, j \in \{1, 2, \dots, n\}$, $S_{i,j} \equiv T_{i,j} \pmod p$, meaning the elements at corresponding positions are congruent.

For a given $B$, let $f(B)$ denote the number of matrices $A$ that satisfy the equation.

However, solving for $f(B)$ given $B$ is too simple, so you need to calculate the sum of $3^{f(B)}$ for all $n \times n$ matrices $B$ that satisfy $|B| \neq 0$ (i.e., invertible or non-singular).

Since this sum can be very large, you need to output the sum modulo a given number $mod$.

Note that only $n, q, mod$ are given.

Input

The first line contains three space-separated positive integers $n, q, mod$.

Output

A single non-negative integer representing the sum modulo $mod$.

Examples

Input 1

2 2 1000000007

Output 1

43046970

Note 1

For matrix $B=\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$, the matrices $A$ satisfying the condition are: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}0 & 0 \\ 1 & 1\end{array}\right),\left(\begin{array}{ll}1 & 1 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}1 & 1 \\ 1 & 1\end{array}\right)$, totaling 4.

For matrix $B=\left(\begin{array}{ll}0 & 1 \\ 1 & 1\end{array}\right)$, the matrix $A$ satisfying the condition is: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$, totaling 1.

For matrix $B=\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$, all matrices $A$ satisfy the condition, totaling 16.

For matrix $B=\left(\begin{array}{ll}1 & 0 \\ 1 & 1\end{array}\right)$, the matrices $A$ satisfying the condition are: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}0 & 0 \\ 1 & 0\end{array}\right),\left(\begin{array}{ll}1 & 0 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}1 & 0 \\ 1 & 0\end{array}\right)$, totaling 4.

For matrix $B=\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right)$, the matrices $A$ satisfying the condition are: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}0 & 0 \\ 0 & 1\end{array}\right),\left(\begin{array}{ll}0 & 1 \\ 0 & 0\end{array}\right),\left(\begin{array}{ll}0 & 1 \\ 0 & 1\end{array}\right)$, totaling 4.

For matrix $B=\left(\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right)$, the matrix $A$ satisfying the condition is: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$, totaling 1.

Thus, the answer is $3^4+3^1+3^{16}+3^4+3^4+3^1 \equiv 43046970\left(\bmod 10^9+7\right)$.

Input 2

100 127 998244353

Output 2

881381862

Note 2

Indeed.

Constraints

For all test cases, $10^8 \le mod \le 10^9+7$, $2 \leq q < mod$, and both $q$ and $mod$ are prime numbers.

This problem uses bundled subtasks. The subtask descriptions and scores are as follows: