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>
using namespace std;
const int mod = 998244353;
template <typename T>
void chkmin(T &x, T y) {
  if (y < x) x = y;
}
template <typename T>
void chkmax(T &x, T y) {
  if (y > x) x = y;
}
template <typename T>
void upd(T &x, T y) {
  if ((x += y) >= mod) x -= mod;
}
int n, m, K, sl, fh, top, ans, s[1000010], c[1000010], L[1000010], f[1000010],
    tr[1000010 << 2];
struct Lim {
  int l, r, x;
  bool operator<(const Lim &p) const {
    return r < p.r || (r == p.r && l <= p.l);
  }
} a[1000010], q[1000010];
int rd() {
  sl = 0;
  fh = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') fh = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') sl = sl * 10 + ch - '0', ch = getchar();
  return sl * fh;
}
void update(int x, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) return (void)(tr[x] |= v);
  if (L <= ((l + r) >> 1)) update(x << 1, l, ((l + r) >> 1), L, R, v);
  if (R > ((l + r) >> 1)) update(x << 1 | 1, ((l + r) >> 1) + 1, r, L, R, v);
}
void query(int x, int l, int r, int v) {
  v |= tr[x];
  if (l == r) return (void)(s[l] = v);
  query(x << 1, l, ((l + r) >> 1), v);
  query(x << 1 | 1, ((l + r) >> 1) + 1, r, v);
}
int main() {
  ios::sync_with_stdio(false);
  n = rd();
  K = rd();
  m = rd();
  ans = 1;
  for (int i = 1; i <= m; ++i) {
    a[i].l = rd();
    a[i].r = rd();
    a[i].x = rd();
    update(1, 1, n, a[i].l, a[i].r, a[i].x);
  }
  query(1, 1, n, 0);
  for (int p, w, i = 0; i < K; ++i) {
    for (int j = 1; j <= n; ++j) L[j] = f[j] = 0, c[j] = (s[j] >> i) & 1;
    for (int j = 1; j <= m; ++j)
      if (!((a[j].x >> i) & 1)) chkmax(L[a[j].r], a[j].l);
    for (int j = 1; j < n; ++j) chkmax(L[j + 1], L[j]);
    p = 0;
    w = 1;
    f[0] = 1;
    for (int j = 1; j <= n; ++j) {
      if (!c[j]) f[j] = w;
      upd(w, f[j]);
      for (; p < L[j]; ++p) upd(w, mod - f[p]);
    }
    ans = 1ll * w * ans % mod;
  }
  printf("%d\n", ans);
  return 0;
}
