Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Counting Matrices

By jackal_1586 · Limits 1s, 512 MB

Given a natural number NN and a prime pp, let’s define a special set Zp={0,1,2,,p1}Z_p = \{0, 1, 2, \dots, p-1\}. Now count the number of different N×NN\times N invertible matrices where the entries of every matrices are from the set ZpZ_p. That is the entries of the matrix are between 00 to p1p-1 and all operations are done modulo pp. To further elaborate this, a brief overview of the operations that can be performed are as follows:

  1. Vector addition: let x=[x1 x2  xN]Tx=[x_1\ x_2\ \dots\ x_N]^T and y=[y1 y2  yN]Ty=[y_1\ y_2\ \dots\ y_N]^T be any two vectors of size N×1N\times 1. Then we can add xx and yy as x+y=[(x1+y1)(modp) (x2+y2)(modp)  (xN+yN)(modp)]Tx+y=[(x_1+y_1) \pmod{p}\ (x_2+y_2) \pmod{p}\ \dots\ (x_N+y_N)\pmod{p}]^T.

  2. Scalar multiplication: For any x=[x1 x2  xN]Tx=[x_1\ x_2\ \dots\ x_N]^T and aZpa\in Z_p, we can multiply aa with xx as ax=[(ax1)(modp) (ax2)(modp)  (axN)(modp)]Tax=[(ax_1)\pmod{p}\ (ax_2)\pmod{p}\ \dots\ (ax_N) \pmod{p}]^T.

Similarly, since a N×NN\times N matrix is a ordered set of NNcolumn vector, we can say addition of two matrices, multiplication of a matrix by a scalar, and matrix multiplication will be done in similar fashion that the formula for each entry is evaluated modulo pp.

Invertible matrix is one which has non zero determinant, equivalently it has N linearly independent rows/columns.

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix AA, denoted det(A)det(A) which is calculated by the following procedure:

If the matrix is 1×11\times 1, then det(A)=a11det(A)=a_{11}. Otherwise for any N×NN\times N matrix, det(A)=(m=1m=N(1)m+1aijdet(Aij))(modp)det(A) = \left(\sum\limits_{m=1}^{m=N}(-1)^{m+1}a_{ij}det(A_{ij})\right)\pmod{p}. Here, aija_{ij} is the entry of ithi^{th} row and jthj^{th} column of the matrix, and AijA_{ij} is the (N1)×(N1)(N-1)\times (N-1)matrix obtained by removing the ithi^{th} row and jthj^{th} column of AA.

A set of vectors (row/column) B={v1,v2,,vN}B= \{v_1, v_2, \dots, v_N\} is called linearly independent when m=1Namvm=0\sum\limits_{m =1}^{N}a_mv_m = 0 if and only if am=0a_m=0 for all m{1,2,,N}m\in\{1, 2, \dots, N\}is true. For example: v1=[1 1],v2=[1 1]v_1=[1\ 1], v_2=[-1\ -1] are not linearly independent as v1+v2=0 v_1+v_2=0 thus a1=a2=1 a_1=a_2=1 also makes the sum 00.

Input

First line of the input contains an integer T(0<T<101)T (0< T <101) denoting the number of test cases to be followed. Each of the next TT lines contain two integers N(1<N<1000001)N (1<N<1000001) and p(1<p<10000001)p (1<p<10000001). You need to count the number of N×NN\times Ninvertible matrices with entries from ZpZ_p. You are guaranteed that the pp in input is a prime number.

Output

For each case, print the number of N×NN\times Ninvertible matrices in the given setup in a separate line. Since the numbers can be pretty big, print your answer modulo 998244353998244353.

Sample

InputOutput
2
2 3
2 2
48
6

In sample input of 2 2, the valid matrices are the following:

[1001]\begin{bmatrix}1 & 0 \\ 0 & 1 \end{bmatrix}, [0110]\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}, [1110]\begin{bmatrix}1 & 1 \\ 1 & 0 \end{bmatrix}, [1101]\begin{bmatrix}1 & 1 \\ 0 & 1 \end{bmatrix}, [0111]\begin{bmatrix}0 & 1 \\ 1 & 1 \end{bmatrix}, [1011]\begin{bmatrix}1 & 0 \\ 1 & 1 \end{bmatrix}.

Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Editorial

We will use the concept of span to make our argument concise. Read if you don’t know what a span is:...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.