E. Not Another Linear Algebra Problem
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

What age is it that you are still solving traditional linear algebra problem?

You are given a prime number $$$q$$$.

Suppose $$$A$$$ and $$$B$$$ are two $$$n \times n$$$ square matrices such that $$$AB \equiv A \pmod q$$$, and each element of $$$A$$$ and $$$B$$$ is an integer from $$$0$$$ to $$$q-1$$$.

  • Here, $$$S \equiv T \pmod q$$$ implies that for each $$$1 \leq i,j \leq n$$$, we have $$$S_{i,j} \equiv T_{i,j} \pmod q$$$.

Given a fixed matrix $$$B$$$ ($$$\det B \ne 0$$$), it's too easy for you to just find an arbitrary suitable matrix $$$A$$$.

Let $$$f(B)$$$ represent the number of matrices that satisfy the equation above. Your task is to calculate:

$$$$$$\sum_{B \in M_n(\mathbb F_q)} [\det B \ne 0] 3^{f(B)}$$$$$$

The answer can be quite large, you only need to output it modulo another given prime number, $$$mod$$$.

Input

The first line of the input contains three integers $$$n$$$, $$$q$$$ and $$$mod$$$. ($$$1 \leq n \leq 10^7$$$, $$$2 \leq q \lt mod$$$, $$$10^8 \leq mod \leq 10^9+7$$$).

It is guaranteed that $$$q$$$ and $$$mod$$$ are two prime numbers.

Output

Output a single line contains a single integer, indicating the answer modulo the given number $$$mod$$$.

Examples
Input
2 2 1000000007
Output
43046970
Input
100 127 998244353
Output
881381862
Note

For $$$B=\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$$$, matrices $$$A$$$ that satisfy 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 $$$B=\left(\begin{array}{ll}0 & 1 \\ 1 & 1\end{array}\right)$$$, the matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, totaling 1.

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

For $$$B=\left(\begin{array}{ll}1 & 0 \\ 1 & 1\end{array}\right)$$$, matrices $$$A$$$ that satisfy 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 $$$B=\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right)$$$, matrices $$$A$$$ that satisfy 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 $$$B=\left(\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right)$$$, the matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, totaling 1.

Therefore, the answer is $$$3^4+3^1+3^{16}+3^4+3^4+3^1 \equiv 43046970 \pmod {(10^9+7)}$$$.