We will solve the problem for each bit separately, and then multiply the results.

Obviously, if the position is covered by a segment with the value 1, then we have no choice, and we must put 1 there. For segments with the value 0, there must be at least one position that they cover and its value is 0.

So we can write the following dynamic programming: dpi — the number of arrays such that the last 0 was exactly at the position i, and all 0-segments to the left of it contain at least one zero.

It remains to determine which states j we can update from. The only restriction we have is that there should not be any segment (l,r) with the value 0, such that j<l and r<i. Since in this case, this segment will not contain any zero values. For each position i, we may precalculate the rightmost position fi where some segment ending before i begins, and while calculating dpi, we should sum up only the values starting from position fi. This can be done with prefix sums.

#include<bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, K, M; cin >> N >> K >> M;
    vector<vector<pair<int, int>>> constraints(N);
    for (int i = 0; i < M; i++) {
        int l, r, x; cin >> l >> r >> x; l--, r--;
        constraints[r].emplace_back(l, x);
    }
    int64_t totAns = 1;
    vector<pair<int, int>> dp(N+1);
    for (int k = 0; k < K; k++) {
        int lo,hi;
        int totDp = (dp[lo = hi = 0] = {-1,1}).second;
        for (int i = 0; i < N; i++) {
            totDp += (dp[++hi] = {i,totDp}).second;
            if (totDp >= MOD) totDp -= MOD;
            for (auto it : constraints[i]) {
                if (it.second & (1<<k)) {
                    while (lo <= hi && dp[hi].first >= it.first) {
                        totDp -= dp[hi--].second;
                        if (totDp < 0) totDp += MOD;
                    }
                } else {
                    while (lo <= hi && dp[lo].first < it.first) {
                        totDp -= dp[lo++].second;
                        if (totDp < 0) totDp += MOD;
                    }
                }
            }
        }
        totAns *= totDp;
        totAns %= MOD;
    }
    cout << totAns << '\n';

    return 0;
}


int one[MX], zero[MX];
int bit[MX];
ll dp[MX];



int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    int K; cin >> K;
    cin >> M;

    ll ans = 1;

    vector<vi> conds; F0R(i, M) {
        int A, B, C; cin >> A >> B >> C;
        A--; B--; C = (1 << K) - 1 - C;
        conds.pb({A, B, C});
    }


    F0R(x, K) {
        F0R(i, N) {
            one[i] = -1, zero[i] = -1;
        }
        F0R(i, M) {
            if (conds[i][2] & (1 << x)) {
                one[conds[i][1]] = max(one[conds[i][1]], conds[i][0]);

            } else {
                zero[conds[i][0]] = max(zero[conds[i][0]], conds[i][1]);
            }
        }

        ll sum = 1;
        int p = 0;
        dp[0] = 1;
        int zed = 0;
        FOR(i, 1, N+1) {
            dp[i] = sum;
            zed = max(zed, zero[i-1] + 1);
            if (zed >= i) {
                dp[i] = 0;
            }
            sum += dp[i]; sum %= MOD;
            while (p <= one[i-1]) {
                sum += MOD - dp[p];
                sum %= MOD;
                p++;
            }
        }

        ans *= sum; ans %= MOD;
        F0R(i, N) {
            //cout << x << " " << i << " " << one[i] << " " << zero[i] << endl;
        }
        //cout << sum << endl;


    }

    cout << ans << endl;

    return 0;
}