Page Contents

## Curious Matrix CURMAT SOLUTION Code Chef

You are given a prime p and a matrix M with N rows (numbered 1 through N) and N columns (numbered 1 through N). For each row r and column c, the cell in row r and column c can either be empty or contain an integer Mr,c. Initially, all cells are empty.

**Curious Matrix CURMAT SOLUTION**Now you should process Q queries. In each query, you are given integers x, y and v and you should do the following:

If the cell (x,y) is empty before this query, put the value v in it, i.e. set Mx,y to v.

Otherwise, i.e. if the cell (x,y) is not empty, make this cell empty again. It is guaranteed that in such a case, Mx,y=v before this query; v is provided for convenience.

*Curious Matrix CURMAT SOLUTION*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+7.

*Curious Matrix CURMAT SOLUTION*In particular, when there are no empty cells in the matrix, the answer is 1 if the matrix is curious or 0 if it is not curious.

In a curious matrix:

Each cell contains an integer between 1 and p−1 inclusive.

For each non-trivial square submatrix A of M (a submatrix containing more than one cell), its determinant |A| is a multiple of p.

For example, consider the following matrix.

- A=⎡⎣⎢122244122⎤⎦⎥
- This matrix is curious. For the prime p=5, each of the elements of the matrix is in the range [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 0.
*Curious Matrix CURMAT SOLUTION* - B=[3114]
- The above matrix is not a curious matrix for p=5, since the determinant of the only non-trivial square submatrix (which is the whole matrix) is 11, not a multiple of p.

Input

The first line of the input contains three space-separated integers N, Q and p.

Q lines follow. Each of these lines contains three space-separated integers x, y and v 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+7.

Constraints

2≤N≤105

1≤Q≤105

2≤p≤998,244,353

p is a prime number

1≤x,y≤N

1≤v≤p−1

Subtasks

- Subtask #1 (20 points): 1≤N,Q≤300
- Subtask #2 (20 points): no two queries affect the same cell, i.e. the pairs (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 4-th query, the matrix is completely filled, but it is not curious for p=5, so the answer is 0.
- After the 5-th query, there are 3 filled cells: (1,1)→3, (2,1)→1 and (2,2)→4. The cell (1,2) is empty and if we want the determinant of the matrix to be divisible by p=5, we have to put 2 in this cell. Then the determinant is 3⋅4−1⋅2=10.

### January Long Challenge 2021

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

## 4 thoughts on “Curious Matrix CURMAT SOLUTION Code Chef”