Score : 900 points
Takahashi has an N \times N grid. The square at the i-th row and the j-th column of the grid is denoted by (i,j). Particularly, the top-left square of the grid is (1,1), and the bottom-right square is (N,N).
An integer, 0 or 1, is written on M of the squares in the Takahashi's grid. Three integers a_i,b_i and c_i describe the i-th of those squares with integers written on them: the integer c_i is written on the square (a_i,b_i).
Takahashi decides to write an integer, 0 or 1, on each of the remaining squares so that the condition below is satisfied. Find the number of such ways to write integers, modulo 998244353.
Input is given from Standard Input in the following format:
N M a_1 b_1 c_1 : a_M b_M c_M
Print the number of possible ways to write integers, modulo 998244353.
3 3 1 1 1 3 1 0 2 3 1
8
For example, the following ways to write integers satisfy the condition:
101 111 011 111 000 011
4 5 1 3 1 2 4 0 2 3 1 4 2 1 4 4 1
32
3 5 1 3 1 3 3 0 3 1 0 2 3 1 3 2 1
0
4 8 1 1 1 1 2 0 3 2 1 1 4 0 2 1 1 1 3 0 3 4 1 4 4 1
4
100000 0
342016343