#P18691. Not Another Linear Algebra Problem
Not Another Linear Algebra Problem
Not Another Linear Algebra Problem
都什么年代了,你怎么还在做传统的线性代数题?
给定一个素数 。设 是两个 的方阵,矩阵的每个元素都是 至 的整数,并且满足
这里 表示,对所有 ,均有 。
给定一个固定的可逆矩阵 ,仅仅找出任意一个满足等式的矩阵 ,对你来说实在太容易了。
令 表示满足上述等式的矩阵 的数量。你的任务是计算
$$\sum_{B\in M_n(\mathbb F_q)}[\det B\ne0]\,3^{f(B)}.$$其中 是有限域 上所有 矩阵的集合;方括号内条件成立时为 1,否则为 0。因此只对在 上可逆的 求和, 不要求可逆。
答案可能很大,请输出它对另一个给定素数 取模后的结果。
输入格式
一行包含三个整数 ,满足
$$1\le n\le10^7,\qquad 2\le q<\mathrm{mod},\qquad10^8\le\mathrm{mod}\le10^9+7.$$保证 和 都是素数。输入只有一组数据。
输出格式
输出一行一个整数,表示答案对给定的 取模后的结果。
样例 1 输入
2 2 1000000007
样例 1 输出
43046970
样例 2 输入
100 127 998244353
样例 2 输出
881381862
样例 1 说明
在 上,六个可逆的 及对应的全部满足条件的 如下。
对于 ,满足条件的 为
$$\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 个。
对于 ,只有零矩阵 满足条件,共有 1 个。
对于 ,所有 矩阵 都满足条件,共有 16 个。
对于 ,满足条件的 为
$$\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 个。
对于 ,满足条件的 为
$$\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 个。
对于 ,只有零矩阵 满足条件,共有 1 个。
因此,答案为
$$3^4+3^1+3^{16}+3^4+3^4+3^1\equiv43046970\pmod{10^9+7}.$$