問題文

以下の条件を満たす $N\times N$ の行列の個数を求めてください。行列の $i$ 行 $j$ 列の値を $a_{i,j}$ とします。

• 全ての正整数の組 $i,j(1\le i,j\le N)$ に対して $a_{i,j}$ は $0$ か $1$ の内どちらかである。
• 全ての $i(1\le i\le M)$ に対して $a_{x_i,y_i}=z_i$ が成り立つ。
• 行列から任意の $2\times 2$ 以上の正方形領域を選ぶとその部分の行列の値の総和は選んだ正方形領域の $1$ 辺の長さと偶奇が等しい。厳密には、正整数の組 $X,Y,K$ に対して、${\displaystyle \sum _{i=X}^{X+K-1}\sum _{j=Y}^{Y+K-1}{a}_{i,j}\equiv K(\mathrm{mod}2)}$ が成り立つ。 ただし、$X,Y,K$ は $1\le X\le N,1\le Y\le N,2\le K\le N,1\le X+K-1\le N,1\le Y+K-1\le N$ を満たすもののみ考える。

ただし、解は非常に大きくなる可能性があるので $998244353$ で割った余りを出力してください。

入力

$NM$
$x_1{y}_1{z}_1$
$x_2{y}_2{z}_2$
$⋮$
$x_M{y}_M{z}_M$

• 入力は全て整数である。
• $1\le N\le {10}^5$
• $0\le M\le 100$
• $1\le x_i,y_i\le N$
• $i\ne j$ ならば $(x_i,y_i)\ne (x_j,y_j)$
• $0\le z_i\le 1$

出力

条件を満たす行列の個数を出力してください。ただし、解は非常に大きくなるかもしれないので $998244353$ で割った余りを出力してください。

サンプル

2 0

8

1 1
0 0

0 1
1 0

100000 4
1 1 0
1 2 0
2 1 0
2 2 1

0