p03199 CADDi 2018 - Square
Takahashi has an N \times N grid. The square at the i-th row and the j-th column of the grid is denoted by (i,j). Particularly, the top-left square of the grid is (1,1), and the bottom-right square is (N,N).

An integer, 0 or 1, is written on M of the squares in the Takahashi's grid. Three integers a_i,b_i and c_i describe the i-th of those squares with integers written on them: the integer c_i is written on the square (a_i,b_i).

Takahashi decides to write an integer, 0 or 1, on each of the remaining squares so that the condition below is satisfied. Find the number of such ways to write integers, modulo 998244353.

* For all 1\leq i < j\leq N, there are even number of 1s in the square region whose top-left square is (i,i) and whose bottom-right square is (j,j).

Constraints

* 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)
* If i \neq j, then (a_i,b_i) \neq (a_j,b_j).
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1 c_1
:
a_M b_M c_M


Output

Print the number of possible ways to write integers, modulo 998244353.

Examples

Input

3 3
1 1 1
3 1 0
2 3 1


Output

8


Input

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


Output

32


Input

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


Output

0


Input

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


Output

4


Input

100000 0


Output

342016343
```python
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・適当な部分空間なので、達成可能でありさえすれば数え上げは簡単
・対角成分に関して向かい側はまとめる。「必ず0」「必ず1」「free」
・対角から遠いところについては調整不可能。「必ず1」がここにあると死亡
・そうでない場合、対角～対角+2までを矛盾なく作れれば勝ち
"""

import itertools

MOD = 998244353

N,M = map(int,readline().split())
m = map(int,read().split())
ABC = list(zip(m,m,m))

# ある：10点
from collections import defaultdict
counter = defaultdict(int)
for a,b,c in ABC:
    if a>b:
        a,b = b,a
    counter[(a,b)] += 10+c

diag0 = [-1] * N
diag1 = [-1] * N # 後ろに足す
diag2 = [-1] * N # 前後に足す
free = N*(N-1)//2 # （盤面に対して対角ごとの和をとったもの）ごとの自由度
other = []
for (x,y),n in counter.items():
    if x>y:
        x,y = y,x
    d = y-x
    if d == 0:
        diag0[x-1] = n-10
        continue
    n = -1 if n<20 else n&1 # 未確定(-1) or 確定(0,1)
    if d >= 3:
        other.append(n)
    elif d == 1:
        diag1[x-1] = n
    elif d == 2:
        diag2[x-1] = n
    else:
        raise Exception

if 1 in other:
    print(0)
    exit()

for i,x in enumerate(diag2[:-2]):
    if x == -1:
        continue
    y = diag0[i+1]
    if y == -1:
        diag0[i+1] = x # 対角成分が強制される
        continue
    # どちらも強制されている
    if x != y:
        print(0)
        exit()

"""
diag0, diag1 の状態を元に、完成図の通り数を数える。
列ごとに処理。対角成分に書き込まれるのが、0のときa通り、1のときb通り
"""

if diag0[0] == -1:
    dp = [1,1]
elif diag0[0] == 0:
    dp = [1,0]
else:
    dp = [0,1]
for x0,x1 in zip(diag0[1:],diag1[:-1]):
    it0 = ([0],[1],[0,1])[x0]
    it1 = ([0],[1],[0,1])[x1]
    prev = dp
    dp = [0,0]
    for y0,y1 in itertools.product(it0,it1):
        dp[y0] += prev[y0^y1]
    if dp[0] > MOD: dp[0] -= MOD
    if dp[1] > MOD: dp[1] -= MOD

x = dp[0] + dp[1] # 完成盤面+transepose(完成盤面)が何通りあるか

# あとは、指定状態を固定したときの自由度
free = N*(N-1)//2
for (r,c),n in counter.items():
    if r == c:
        continue
    if n >= 10:
        free -= 1

answer = x * pow(2,free,MOD) % MOD
print(answer)
```