题目背景

$shik$ 搞核工程去了。

题目描述

$127$ 想要考考你解方程的能力。

你有这样一个方程：$AB \equiv A \pmod q$，其中 $q$ 为素数，且满足 $A,B$ 为 $n$ 阶方阵，并且矩阵中的元素 $\in \{0,1,2,...,q−1\}$（之后的所有矩阵也要满足这一点）。

方阵的同余 $S \equiv T \pmod p$ 被定义为 $\forall i,j \in \{1,2,...,n\}$，$S_{i,j} \equiv T_{i,j} \pmod p$，即对应位置同余。

对于这样的给定的 $B$，记 $f(B)$ 表示使方程同余的所有 $A$ 的数量。

但是给定一个 $B$ 求解 $f(B)$太简单了，所以你需要对满足 $|B| \ne 0$（或者说可逆，非奇异）的 $n$ 阶方阵求解 $3^{f(B)}$ 的和。

并且由于这个和太大了，你需要将这个和对一个给定的数 $mod$ 取模。

注意，只有 $n,q,mod$ 是给定的。

输入格式

第一行包含三个用空格隔开的正整数 $n,q,mod$。

输出格式

一行一个非负整数代表题面中的和对 $mod$ 取模后的答案。

样例数据

样例 1 输入

2 2 1000000007

样例 1 输出

43046970

样例 1 解释

对于矩阵 $B=\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$, 满足条件的 $A$ 有: $\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)$, 共 4 个

对于矩阵 $B=\left(\begin{array}{ll}0 & 1 \\ 1 & 1\end{array}\right)$, 满足条件的 $A$ 有: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$, 共 1 个

对于矩阵 $B=\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$, 满足条件的 $A$ 为所有的 $A$ 共 16 个

对于矩阵 $B=\left(\begin{array}{ll}1 & 0 \\ 1 & 1\end{array}\right)$, 满足条件的 $A$ 有: $\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)$, 共 4 个

对于矩阵 $B=\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right)$, 满足条件的 $A$ 有: $\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)$, 共 4 个

对于矩阵 $B=\left(\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right)$, 满足条件的 $A$ 有: $\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$, 共 1 个

故答案为 $3^4+3^1+3^{16}+3^4+3^4+3^1 \equiv 43046970\left(\bmod 10^9+7\right)$

样例 2 输入

100 127 998244353

样例 2 输出

881381862

样例解释二

的确如此

限制与约定

对于所有测试点,有 $10^8 \le mod \le 10^9+7$，$2 \leq q < mod$，且满足 $q,mod$ 为素数

本题采用子任务捆绑测试,子任务描述及具体分值如下: