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;
struct P {
  int x, y, z;
  bool operator<(const P &a) const { return y > a.y; };
};
int a, b, c, d, i, k, n, m, e, dx[10] = {1, 0, -1, 0, 1, 1, -1, -1},
                               dy[10] = {0, 1, 0, -1, 1, -1, 1, -1};
long long o[500101];
int l[500111];
int j[201001];
long long x, y, z, mod = 998244353;
string r;
P u[500101];
queue<int> q;
stack<int> s;
map<int, int> p;
vector<int> v;
bool as(P a, P b) {
  if (a.x != b.x) return a.x < b.x;
  return a.y > b.y;
}
int main() {
  scanf("%d %d %d", &a, &b, &c);
  for (int t = 1; t <= c; t++) {
    scanf("%d %d %d", &n, &m, &k);
    u[t] = {n, m, k};
  }
  sort(u + 1, u + c + 1, as);
  z = 1;
  for (int i = 0; i < b; i++) {
    e = 0;
    for (int t = 1; t <= a + 1; t++) l[t] = o[t] = 0;
    for (int t = 1; t <= c; t++)
      if (u[t].z & (1 << i)) {
        int p;
        for (p = max(e + 1, u[t].x); p <= u[t].y; p++) l[p] = 1;
        e = p - 1;
      }
    e = a + 1;
    n = a;
    o[a + 1] = 1;
    x = 1;
    for (int t = c; t; t--)
      if ((u[t].z & (1 << i)) == 0 && u[t].x <= n) {
        for (; n > u[t].y; n--)
          if (!l[n]) o[n] = x, x *= 2, x %= mod;
        for (; n >= u[t].x; n--)
          if (!l[n]) {
            o[n] = x, x *= 2, x %= mod;
          }
        for (; e > u[t].y; e--) x = (x - o[e] + mod) % mod;
      }
    for (; n >= 1; n--)
      if (!l[n]) x *= 2, x %= mod;
    z *= x, z %= mod;
  }
  printf("%lld", z);
}
