设 \(f_{i,j}\) 为恰好 \(i\) 行 \(j\) 列不满足条件的矩阵个数， \(g_{i,j}\) 为钦定 \(i\) 行 \(j\) 列不满足条件的矩阵个数。

容易得到：

\[g_{x,y}=\binom n x \binom n y (k-1)^{n^2-(n-x)(n-y)}k^{(n-x)(n-y)} \]

\[g_{x,y}=\sum_{i=x}^n\sum_{j=y}^n\binom i x\binom j y f_{i,j} \]

根据二元二项式反演有：

\[f_{x,y}=\sum_{i=x}^n\sum_{j=y}^n\binom i x\binom j y(-1)^{i+j-x-y}g_{i,j} \]

我们要求的是 \(f_{0,0}\)，也就是：

\[\sum_{i=0}^n\sum_{j=0}^n\binom i 0\binom j 0\binom n i\binom n j(-1)^{i+j}(k-1)^{n^2-(n-i)(n-j)}k^{(n-i)(n-j)} \]

\[\sum_{i=0}^n\sum_{j=0}^n\binom n i\binom n j(-1)^{i+j}(k-1)^{n^2-n^2+ni+nj-ij}k^{n^2-ni-nj+ij} \]

\[k^{n^2}\sum_{i=0}^n\sum_{j=0}^n\binom n i\binom n j(-1)^{i+j}(\frac {k-1} k)^{ni+nj-ij} \]

为了方便，以下设 \(a=\frac {k-1} k\)。

做法1

有 \(ij=\binom {i+j} 2-\binom i 2-\binom j 2\)，所以：

\[k^{n^2}\sum_{i=0}^n\sum_{j=0}^n\binom n i\binom n j(-1)^{i+j}a^{ni+nj-\binom {i+j} 2+\binom i 2+\binom j 2} \]

\[k^{n^2}n!^2\sum_{i=0}^n\sum_{j=0}^n\frac 1 {i!(n-i)!}\frac 1 {j!(n-j)!}(-1)^{i+j}a^{ni+nj-\binom {i+j} 2+\binom i 2+\binom j 2} \]

设：

\[F_i=\frac {(-1)^ia^{ni+\binom i 2}} {i!(n-i)!} \]

\[G_x=\sum_{i=0}^xF_i \times F_{x-i} \]

答案即为：

\[k^{n^2}n!^2\sum_{i=0}^{2n}G_i \times a^{-\binom i 2} \]

然后我们有 \(a^{\binom n 2}= \prod_{i=1}^{n-1}a^i\)，可以线性递推 \(a^{ni}\) 和 \(a^{\binom i 2}\)。

使用 MTT 计算 \(G\) 即可 \(O(\log mod+n\log n)\) 计算答案。

做法2

\[k^{n^2}\sum_{i=0}^n\sum_{j=0}^n\binom n i\binom n j(-1)^{i+j}a^{ni+(n-i)j} \]

\[k^{n^2}\sum_{i=0}^n\binom n i(-1)^ia^{ni}\sum_{j=0}^n\binom n j(-1)^ja^{(n-i)j} \]

\[k^{n^2}\sum_{i=0}^n\binom n i(-1)^ia^{ni}(1-a^{n-i})^n \]

\[k^{n^2}\sum_{i=0}^n\binom n i(-1)^i(a^i-a^n)^n \]

预处理 \(a^1 \sim a^n\) 即可 \(O(n\log n+\log mod)\)。