Curious Matrix CURMAT SOLUTION Code Chef

Curious Matrix CURMAT SOLUTION Code Chef

You are given a prime pp and a matrix MM with NN rows (numbered 11 through NN) and NN columns (numbered 11 through NN). For each row rr and column cc, the cell in row rr and column cc can either be empty or contain an integer Mr,cMr,c. Initially, all cells are empty.

Now you should process QQ queries. In each query, you are given integers xx, yy and vv and you should do the following:

  • If the cell (x,y)(x,y) is empty before this query, put the value vv in it, i.e. set Mx,yMx,y to vv.
  • Otherwise, i.e. if the cell (x,y)(x,y) is not empty, make this cell empty again. It is guaranteed that in such a case, Mx,y=vMx,y=v before this query; vv is provided for convenience.
  • Afterwards, Chef wants you to find the number of ways to fill all empty cells with (not necessarily the same) integers in such a way that the resulting matrix is curious. Since this number may be large, compute it modulo 109+7109+7.

In particular, when there are no empty cells in the matrix, the answer is 11 if the matrix is curious or 00 if it is not curious.

In a curious matrix:

  • Each cell contains an integer between 11 and p−1p−1 inclusive.
  • For each non-trivial square submatrix AA of MM (a submatrix containing more than one cell), its determinant |A||A| is a multiple of pp.

For example, consider the following matrix.A=⎡⎣⎢122244122⎤⎦⎥A=[121242242]

This matrix is curious. For the prime p=5p=5, each of the elements of the matrix is in the range [1,p−1][1,p−1]. Also, the determinant of each non-trivial square submatrix (there are five of them) is a multiple of the given prime ― for example, the determinant of the whole matrix is 00.B=[3114]B=[3114]

The above matrix is not a curious matrix for p=5p=5, since the determinant of the only non-trivial square submatrix (which is the whole matrix) is 1111, not a multiple of pp.

Input

  • The first line of the input contains three space-separated integers NN, QQ and pp.
  • QQ lines follow. Each of these lines contains three space-separated integers xx, yy and vv describing a query.

Output

After performing each query, print a single line containing one integer ― the number of ways to form a curious matrix, modulo 109+7109+7.

Constraints

  • 2≤N≤1052≤N≤105
  • 1≤Q≤1051≤Q≤105
  • 2≤p≤998,244,3532≤p≤998,244,353
  • pp is a prime number
  • 1≤x,y≤N1≤x,y≤N
  • 1≤v≤p−11≤v≤p−1

Subtasks

Subtask #1 (20 points): 1≤N,Q≤3001≤N,Q≤300

Subtask #2 (20 points): no two queries affect the same cell, i.e. the pairs (x,y)(x,y) for all queries are pairwise distinct

Subtask #3 (20 points): after each query, there is at least one way to construct a curious matrix

Subtask #4 (40 points): original constraints

Example Input

2 6 5
1 1 3
1 2 1
2 1 1
2 2 4
1 2 1
2 2 4

Example Output

16
4
1
0
1
4

Explanation

The only non-trivial square submatrix here is the whole matrix.

In the 44-th query, the matrix is completely filled, but it is not curious for p=5p=5, so the answer is 00.

After the 55-th query, there are 33 filled cells: (1,1)→3(1,1)→3, (2,1)→1(2,1)→1 and (2,2)→4(2,2)→4. The cell (1,2)(1,2) is empty and if we want the determinant of the matrix to be divisible by p=5p=5, we have to put 22 in this cell. Then the determinant is 3⋅4−1⋅2=103⋅4−1⋅2=10.

Solution

January Long Challenge 2021

Leave a Comment