#P18691. Not Another Linear Algebra Problem

Not Another Linear Algebra Problem

Not Another Linear Algebra Problem

都什么年代了,你怎么还在做传统的线性代数题?

给定一个素数 qq。设 A,BA,B 是两个 n×nn\times n 的方阵,矩阵的每个元素都是 00 至 q−1q-1 的整数,并且满足

AB≡A(modq).AB\equiv A\pmod q.

这里 S≡T(modq)S\equiv T\pmod q 表示,对所有 1≤i,j≤n1\le i,j\le n,均有 Si,j≡Ti,j(modq)S_{i,j}\equiv T_{i,j}\pmod q。

给定一个固定的可逆矩阵 BB,仅仅找出任意一个满足等式的矩阵 AA,对你来说实在太容易了。

令 f(B)f(B) 表示满足上述等式的矩阵 AA 的数量。你的任务是计算

$$\sum_{B\in M_n(\mathbb F_q)}[\det B\ne0]\,3^{f(B)}.$$

其中 Mn(Fq)M_n(\mathbb F_q) 是有限域 Fq\mathbb F_q 上所有 n×nn\times n 矩阵的集合;方括号内条件成立时为 1,否则为 0。因此只对在 Fq\mathbb F_q 上可逆的 BB 求和,AA 不要求可逆。

答案可能很大,请输出它对另一个给定素数 mod\mathrm{mod} 取模后的结果。

输入格式

一行包含三个整数 n,q,modn,q,\mathrm{mod},满足

$$1\le n\le10^7,\qquad 2\le q<\mathrm{mod},\qquad10^8\le\mathrm{mod}\le10^9+7.$$

保证 qq 和 mod\mathrm{mod} 都是素数。输入只有一组数据。

输出格式

输出一行一个整数,表示答案对给定的 mod\mathrm{mod} 取模后的结果。

样例 1 输入

2 2 1000000007

样例 1 输出

43046970

样例 2 输入

100 127 998244353

样例 2 输出

881381862

样例 1 说明

在 F2\mathbb F_2 上,六个可逆的 BB 及对应的全部满足条件的 AA 如下。

对于 B=(0110)B=\begin{pmatrix}0&1\\1&0\end{pmatrix},满足条件的 AA 为

$$\begin{pmatrix}0&0\\0&0\end{pmatrix},\quad \begin{pmatrix}0&0\\1&1\end{pmatrix},\quad \begin{pmatrix}1&1\\0&0\end{pmatrix},\quad \begin{pmatrix}1&1\\1&1\end{pmatrix},$$

共有 4 个。

对于 B=(0111)B=\begin{pmatrix}0&1\\1&1\end{pmatrix},只有零矩阵 A=(0000)A=\begin{pmatrix}0&0\\0&0\end{pmatrix} 满足条件,共有 1 个。

对于 B=(1001)B=\begin{pmatrix}1&0\\0&1\end{pmatrix},所有 2×22\times2 矩阵 AA 都满足条件,共有 16 个。

对于 B=(1011)B=\begin{pmatrix}1&0\\1&1\end{pmatrix},满足条件的 AA 为

$$\begin{pmatrix}0&0\\0&0\end{pmatrix},\quad \begin{pmatrix}1&0\\0&0\end{pmatrix},\quad \begin{pmatrix}0&0\\1&0\end{pmatrix},\quad \begin{pmatrix}1&0\\1&0\end{pmatrix},$$

共有 4 个。

对于 B=(1101)B=\begin{pmatrix}1&1\\0&1\end{pmatrix},满足条件的 AA 为

$$\begin{pmatrix}0&0\\0&0\end{pmatrix},\quad \begin{pmatrix}0&1\\0&0\end{pmatrix},\quad \begin{pmatrix}0&0\\0&1\end{pmatrix},\quad \begin{pmatrix}0&1\\0&1\end{pmatrix},$$

共有 4 个。

对于 B=(1110)B=\begin{pmatrix}1&1\\1&0\end{pmatrix},只有零矩阵 A=(0000)A=\begin{pmatrix}0&0\\0&0\end{pmatrix} 满足条件,共有 1 个。

因此,答案为

$$3^4+3^1+3^{16}+3^4+3^4+3^1\equiv43046970\pmod{10^9+7}.$$