QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 5031. 核

Statistics

题目背景

$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$ $ $