都什么年代了，还在做传统的线性代数题？

给定一个素数 $q$。 假设 $A$ 和 $B$ 是两个 $n \times n$ 的方阵，满足 $AB \equiv A \pmod q$，且 $A$ 和 $B$ 的每个元素都是 $0$ 到 $q-1$ 之间的整数。

• 这里，$S \equiv T \pmod q$ 意味着对于每个 $1 \le i, j \le n$，都有 $S_{i,j} \equiv T_{i,j} \pmod q$。

给定一个固定的矩阵 $B$（满足 $\det B \neq 0$），让你找出一个任意合适的矩阵 $A$ 实在太简单了。 令 $f(B)$ 表示满足上述方程的矩阵 $A$ 的数量。你的任务是计算：

$$\sum_{B \in M_n(\mathbb{F}_q)} [\det B \neq 0] 3^{f(B)}$$

答案可能非常大，你只需要输出它对另一个给定的素数 $mod$ 取模后的结果。

输入格式

输入的第一行包含三个整数 $n, q$ 和 $mod$。($1 \le n \le 10^7$, $2 \le q < mod$, $10^8 \le mod \le 10^9 + 7$)。 保证 $q$ 和 $mod$ 均为素数。

输出格式

输出一行，包含一个整数，表示答案对给定的数 $mod$ 取模的结果。

样例

样例输入 1

2 2 1000000007

样例输出 1

43046970

样例输入 2

100 127 998244353

样例输出 2

881381862

说明

对于 $B = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$，满足条件的矩阵 $A$ 为：$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$，共 $4$ 个。

对于 $B = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$，满足条件的矩阵 $A$ 为：$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$，共 $1$ 个。

对于 $B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$，所有矩阵 $A$ 都满足条件，共 $16$ 个。

对于 $B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}$，满足条件的矩阵 $A$ 为：$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$，共 $4$ 个。

对于 $B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$，满足条件的矩阵 $A$ 为：$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$，共 $4$ 个。

对于 $B = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$，满足条件的矩阵 $A$ 为：$\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$，共 $1$ 个。

因此，答案为 $3^4 + 3^1 + 3^{16} + 3^4 + 3^4 + 3^1 \equiv 43046970 \pmod{10^9 + 7}$。