题目背景
$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$ 为素数
本题采用子任务捆绑测试,子任务描述及具体分值如下:
| 子任务 | 分值 | $n$ | $q$ | $mod$ |
|---|---|---|---|---|
| $1$ | $10$ | $\le 3$ | $\le 3$ | $ $ |
| $2$ | $20$ | $\le 10^2$ | $ $ | |
| $3$ | $10$ | $\le 3 \cdot 10^3$ | ||
| $4$ | $20$ | $\le 10^6$ | $=998\,244\,353$ | |
| $5$ | $10$ | $\le 10^7$ | $=q+2$ | |
| $6$ | $30$ | $ $ |