题目描述

Takahashi 有一个 $N \times N$ 的网格。网格中第 $i$ 行第 $j$ 列的方块用 $(i,j)$ 表示。特别地，网格的左上角方块是 $(1,1)$，右下角方块是 $(N,N)$。

在 Takahashi 的网格中，有 $M$ 个方块上写有整数 $0$ 或 $1$。用 $a_i,b_i$ 和 $c_i$ 来描述写在这 $M$ 个方块上的整数：方块 $(a_i,b_i)$ 上写着整数 $c_i$。

Takahashi 决定在剩下的方块上分别写入整数 $0$ 或 $1$，以满足以下条件。计算满足条件的写整数方式的数量，取模 $998244353$。

• 对于任意 $1 \leq i < j \leq N$，方块区域 $(i,i)$ 到 $(j,j)$ 之间的方块上的 $1$ 的个数是偶数个。

约束条件

• $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)$。
• 输入中的所有值都是整数。

输入

输入从标准输入给出，格式如下：

$N$ $M$

$a_1$ $b_1$ $c_1$

:

$a_M$ $b_M$ $c_M$

输出

打印满足条件的写整数方式的数量，取模 $998244353$。

输入样例1

3 3
1 1 1
3 1 0
2 3 1

输出样例1

8

例如，满足条件的写整数方式有以下几种：

101   111
011   111
000   011

输入样例2

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

输出样例2

32

输入样例3

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

输出样例3

0

输入样例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

100000 0

输出样例5

342016343