You are given three integers n, k, m and m conditions (l_1, r_1, x_1), (l_2, r_2, x_2), ..., (l_m, r_m, x_m).

Calculate the number of distinct arrays a, consisting of n integers such that: 

  * 0 ≤ a_i < 2^k for each 1 ≤ i ≤ n; 
  * bitwise AND of numbers a[l_i] \& a[l_i + 1] \& ... \& a[r_i] = x_i for each 1 ≤ i ≤ m. 



Two arrays a and b are considered different if there exists such a position i that a_i ≠ b_i. 

The number can be pretty large so print it modulo 998244353.

Input

The first line contains three integers n, k and m (1 ≤ n ≤ 5 ⋅ 10^5, 1 ≤ k ≤ 30, 0 ≤ m ≤ 5 ⋅ 10^5) — the length of the array a, the value such that all numbers in a should be smaller than 2^k and the number of conditions, respectively.

Each of the next m lines contains the description of a condition l_i, r_i and x_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ x_i < 2^k) — the borders of the condition segment and the required bitwise AND value on it.

Output

Print a single integer — the number of distinct arrays a that satisfy all the above conditions modulo 998244353.

Examples

Input


4 3 2
1 3 3
3 4 6


Output


3


Input


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


Output


33

Note

You can recall what is a bitwise AND operation [here](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

In the first example, the answer is the following arrays: [3, 3, 7, 6], [3, 7, 7, 6] and [7, 3, 7, 6].
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
using namespace std;
const long long maxn = 5e5 + 5, MOD = 998244353;
long long ans[maxn], dp[maxn];
bool ma[maxn][31];
long long one[maxn], zero[maxn];
long long F[maxn + 1];
void add(long long pos, long long x) {
  if (!pos) {
    F[0] += x;
    return;
  }
  for (; pos <= maxn; pos += pos & -pos) F[pos] += x;
}
long long get(long long l, long long r) {
  if (l != 1)
    return (get(1, r) - get(1, l - 1) + (l == 0 ? F[0] : 0) + 5ll * MOD) % MOD;
  long long res = 0;
  for (; r > 0; r -= r & -r) res += F[r];
  return res % MOD;
}
signed de[maxn];
struct event {
  signed L, R, B;
};
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, k, m;
  cin >> n >> k >> m;
  long long ANS = 1;
  vector<event> V;
  for (long long i = 0; i < m; i++) {
    signed L, R, X;
    cin >> L >> R >> X;
    V.push_back({L, R, X});
    for (long long j = 0; j < k; j++) ma[i][j] = (X >> j & 1);
  }
  for (long long i = 0; i < k; i++) {
    memset(F, 0, sizeof F);
    memset(one, 0, sizeof one);
    memset(zero, 0, sizeof zero);
    memset(de, 0, sizeof de);
    long long ans = 1;
    for (long long j = 0; j < m; j++) {
      if (ma[j][i])
        one[V[j].L]++, one[V[j].R + 1]--;
      else
        de[V[j].R] = max(de[V[j].R], V[j].L);
    }
    signed LAST = 0;
    for (long long j = 0; j <= maxn; j++) assert(F[j] == 0);
    add(0, 1);
    long long one_ = 0;
    for (long long j = 1; j <= n; j++) {
      one_ += one[j];
      if (!one_) add(j, get(LAST, j - 1));
      LAST = max(LAST, de[j]);
    }
    ANS *= get(LAST, n);
    ANS %= MOD;
  }
  cout << ANS;
}
