Problem Statement

Find the number of $N \times N$ matrices satisfying the following conditions. Let $a_{i,j}$ be the value in row $i$, column $j$ of the matrix.

• For every pair of positive integers $i,j(1 \le i,j \le N)$, $a_{i,j}$ is either $0$ or $1$.
• For every $i(1 \le i \le M)$, $a_{x_i,y_i}=z_i$ holds.
• For any square region of size $2 \times 2$ or larger chosen from the matrix, the sum of the values of the matrix in that part has the same parity as the length of $1$ side of the chosen square region. Formally, for a tuple of positive integers $X,Y,K$, $\displaystyle \sum_{i=X}^{X+K-1} \sum_{j=Y}^{Y+K-1} a_{i,j} \equiv K\pmod 2$ holds. Here, only $X,Y,K$ satisfying $ 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 $ are considered.

Since the answer can be very large, output it modulo $998244353$.

Input

$N\ M$
$x_1\ y_1\ z_1$
$x_2\ y_2\ z_2$
$\vdots$
$x_M\ y_M\ z_M$

• All inputs are integers.
• $1 \le N \le 10^5$
• $0 \le M \le 100$
• $1 \le x_i,y_i \le N$
• If $i \neq j$, then $(x_i,y_i) \neq (x_j,y_j)$
• $0 \le z_i \le 1$

Output

Output the number of matrices satisfying the conditions. Since the answer can be very large, output it modulo $998244353$.

Sample

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