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
/*
[caddi2018] F - Square
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 1e5;
const int MAX_M = 5e4;
const ll MOD = 998244353;

int N, M;
int a[MAX_M], b[MAX_M], c[MAX_M];
map<pii, int> m;
ll dp[MAX_N][2];

bool check(int h, int w, int c) {
    auto kv = m.find(pii(h, w));
    return kv == m.end() || kv->second == c;
}

ll solve() {
    for (int i = 0; i < M; i++) {
        m[pii(a[i], b[i])] = c[i];
    }

    ll cnt = 1LL * (N - 3) * (N - 2);
    for (auto &kv0 : m) {
        int h = kv0.first.first;
        int w = kv0.first.second;
        if (abs(h - w) < 3) {
            continue;
        }
        auto kv1 = m.find(pii(w, h));
        if (kv1 != m.end() && kv0.second != kv1->second) {
            return 0;
        }
        if (kv1 != m.end()) {
            cnt--;
        } else {
            cnt -= 2;
        }
    }

    ll ans = 1;
    ll po = 2;
    for (ll i = cnt / 2; i > 0; i >>= 1) {
        if (i & 1) {
            (ans *= po) %= MOD;
        }
        (po *= po) %= MOD;
    }

    for (int b = 0; b < (1 << 3); b++) {
        int p = (b >> 0) & 1;
        int q = (b >> 1) & 1;
        int r = (b >> 2) & 1;
        int k = (p + q + r) % 2;
        if (check(0, 0, p) && check(0, 1, q) && check(1, 0, r) &&
            check(1, 1, k)) {
            dp[1][k] += 1;
        }
    }
    cerr << "dp[" << 1 << "][" << 0 << "]: " << dp[1][0] << endl;
    cerr << "dp[" << 1 << "][" << 1 << "]: " << dp[1][1] << endl;

    for (int n = 2; n < N; n++) {
        for (int k = 0; k < 2; k++) {
            for (int b = 0; b < (1 << 3); b++) {
                int p = (b >> 0) & 1;
                int q = (b >> 1) & 1;
                int r = (b >> 2) & 1;
                int s = (q + r + k) % 2;
                int t = (p + k) % 2;
                if (check(n - 2, n, p) && check(n - 1, n, q) &&
                    check(n, n, r) && check(n, n - 1, s) &&
                    check(n, n - 2, t)) {
                    (dp[n][r] += dp[n - 1][k]) %= MOD;
                }
            }
        }
        // cerr << "dp[" << n << "][" << 0 << "]: " << dp[n][0] << endl;
        // cerr << "dp[" << n << "][" << 1 << "]: " << dp[n][1] << endl;
    }

    ll ans_d = (dp[N - 1][0] + dp[N - 1][1]) % MOD;
    (ans *= ans_d) %= MOD;

    return ans;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }

    cout << solve() << endl;

    return 0;
}
