問題文

高橋君は、$N$ 行 $N$ 列のマス目を持っています。マス目の上から $i$ 番目、左から $j$ 番目のマスは $(i,j)$ で表されます。 特に、マス目の左上のマスは $(1,1)$ であり、右下のマスは $(N,N)$ です。

高橋君の持っているマス目のうち $M$ 個のマスには、$0$ または $1$ の整数が書き込まれています。 整数が書き込まれたマスのうち $i$ 番目のマスの情報は $3$ つの整数 $a_i,b_i,c_i$ で表され、マス $(a_i,b_i)$ に整数 $c_i$ が書き込まれていることを表します。

高橋君は、以下の条件を満たすように残りのマスに $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