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;
namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
inline int rd() {
  int x = 0;
  char c =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)
           ? EOF
           : *p1++);
  while (!isdigit(c)) {
    c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)
             ? EOF
             : *p1++);
  }
  while (isdigit(c))
    x = x * 10 + (c ^ 48),
    c = (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)
             ? EOF
             : *p1++);
  return x;
}
}  // namespace IO
using namespace IO;
int i, j, k, n, t, a[500500][3], pre[500500], st[500500], ed[500500], x, m, l,
    dp[500500], sum[500500], tmp;
long long ans = 1;
bool one[500500];
int main() {
  dp[0] = sum[0] = 1;
  n = rd();
  x = rd();
  m = rd();
  for (i = 1; i <= m; i++) {
    a[i][1] = rd();
    a[i][2] = rd();
    a[i][0] = rd();
  }
  for (k = 0; k < x; k++) {
    memset(pre, 0, sizeof(pre));
    for (i = 1; i <= m; i++) {
      if ((1 << k) & a[i][0]) {
        st[a[i][1]]++;
        ed[a[i][2]]++;
      } else {
        if (pre[a[i][2]] == 0) {
          pre[a[i][2]] = a[i][1];
        } else {
          pre[a[i][2]] = max(pre[a[i][2]], a[i][1]);
        }
      }
    }
    tmp = 0;
    for (i = 1; i <= n; i++) {
      tmp += st[i];
      if (tmp) {
        one[i] = 1;
      } else {
        one[i] = 0;
      }
      tmp -= ed[i];
      st[i] = ed[i] = 0;
    }
    l = 0;
    for (i = 1; i <= n; i++) {
      dp[i] = sum[i - 1] - ((l == 0) ? 0 : sum[l - 1]);
      dp[i] %= 998244353;
      if (one[i]) {
        dp[i] = 0;
      }
      sum[i] = (sum[i - 1] + dp[i]) % 998244353;
      if (pre[i] > l) {
        l = pre[i];
      }
    }
    ans = ans *
          ((sum[n] % 998244353 - ((l == 0) ? 0 : sum[l - 1] % 998244353)) %
               998244353 +
           998244353) %
          998244353;
  }
  printf("%lld\n", (ans + 998244353) % 998244353);
}
