問題文

$N$ 人の人がいます。それぞれの人は ”正直者” か ”嘘つき” です。

$Q$ 個の主張があります。 $i$ 個目の主張は人 $A_i$ が言ったものです。主張の内容は下記の通りです。

• $($ $C_i=0$ のとき $)$ 人 $B_i$ は ”正直者” である。
• $($ $C_i=1$ のとき $)$ 人 $B_i$ は ”嘘つき” である。

$N$ 人の人の ”正直者” か ”嘘つき” かの組み合わせは $2^N$ 通りあります。これらのうちどの主張とも矛盾がないものの個数を $998244353$ で割った余りを求めてください。

・主張について

”正直者” である人は ”正直者” の人のことを "正直者" であると主張し、 ”嘘つき” のことを ”嘘つき” であると主張します。

”嘘つき” である人は ”正直者” の人のことを "嘘つき" であると主張し、 ”嘘つき” のことを ”正直者” であると主張します。

入力

$N\ \ Q$
$A_1\ \ B_1\ \ C_1$
$A_2\ \ B_2\ \ C_2$
$:$
$A_Q\ \ B_Q\ \ C_Q$

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• $(A_i, B_i) \neq (A_j, B_j) \ (i \neq j)$
• $C_i$ は $0$ か $1$
• 入力は全て整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

4 3
1 2 1
2 3 1
3 1 0

4

3 3
1 2 1
2 3 1
3 1 1

0

172 12
13 29 0
48 127 1
86 25 0
171 68 1
21 67 1
29 86 0
37 23 0
37 163 1
45 48 1
163 127 0
2 13 0
68 22 1

346915093