You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Square

题面翻译

高桥有一个 $N$ 行 $N$ 列的正方形表格，表格的第 $i$ 行第 $j$ 列记为 $(i,j)$ 。 特别地，左上角的方格记为 $(1,1)$ ，右下角的方格记为 $(N,N)$ 。

这个表格中已经有 $M$ 个格子填入了 $0$ 或者 $1$ ，这些填入数字的情况用三个整数 $a_i,b_i,c_i$ 表示，意思是在 $(a_i,b_i)$ 内填入了 $c_i$ 。

高桥想知道，如果在表格内剩下的每个格子都填上 $0$ 或者 $1$ ，满足以下条件的填法总数是多少。答案对 $998244353$ 取模。

• 对任意满足 $1\leq\ i\ <\ j\leq\ N$ 的 $i$ 和 $j$ ，以 $(i,i)$ 为左上角， $(j,j)$ 为右下角的正方形中， $1$ 的个数都是偶数。

输入格式

第一行两个整数 $N,M$ ，接下来 $M$ 行每行三个整数 $a_i,b_i,c_i$ 。

输出格式

一个整数表示答案对 $998244353$ 取模的结果。

样例 #1

样例输入 #1

3 3
1 1 1
3 1 0
2 3 1

样例输出 #1

8

样例 #2

样例输入 #2

4 5
1 3 1
2 4 0
2 3 1
4 2 1
4 4 1

样例输出 #2

32

样例 #3

样例输入 #3

3 5
1 3 1
3 3 0
3 1 0
2 3 1
3 2 1

样例输出 #3

0

样例 #4

样例输入 #4

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

4

样例 #5

样例输入 #5

100000 0

样例输出 #5

342016343

数据范围

$2\ \leq\ N\ \leq\ 10^5$ $0\ \leq\ M\ \leq\ min(5\ \times\ 10^4,N^2)$ $1\ \leq\ a_i,b_i\ \leq\ N(1\leq\ i\leq\ M)$ $0\ \leq\ c_i\ \leq\ 1(1\leq\ i\leq\ M)$ $i\ \neq\ j$ 时必有 $(a_i,b_i)\ \neq\ (a_j,b_j)$

样例解释 1

以下是两种满足条件的填法。

101 
011 
000 

111 
111 
011