Counting Matrices

We will use the concept of span to make our argument concise. Read if you don’t know what a span is: https://en.wikipedia.org/wiki/Linear_span .

Firstly, an invertible $N\times N$ matrix with modulo $p$ entries implies the image of the linear map corresponding to this matrix spans the whole vector space $\mathbb{Z}_p^N$. Let $B$ be any basis for $\mathbb{Z}_p^N$. Basis is the smallest linearly independent set which spans the whole vector space. We claim that for every basis $B$ their is a corresponding invertible matrix $A$. This follows from the rank-nullity theorem, definition of matrix representation of linear transformations. Then our problem becomes to count the number of unique bases of $\mathbb{Z}_p^N$. It is a common trick to extend an empty set to a basis for a vector space in linear algebra. The idea is that we have a basis $C$for some subspace $W$. We pick an element $v$from $\mathbb{Z}_p^N\setminus W$ and continue until $C$ has $N$ vectors in it. Here $W={0}$ means $W$ contains only zero vector. Now, finally we get $C={v_1, v_2, \dots , v_N}$ , where $v_i$ is selected at the $i^{th}$ step of extending the basis. Verify that each $v_i$ can be chosen in $p^N - p^{i-1}$ ways. Hence the final answer is $(p^N-1) (p^N - p) (p^N-p^2)\cdots (p^N-p^{N-1})$ . Now print this modulo $998244353$.