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;
constexpr long long MOD = 998244353;
int mark[500100];
int summark[500100];
int F[500100];
long long dp[500100];
long long sum[500100];
int n;
vector<pair<int, int>> zeros, ones;
bool build() {
  memset(mark, 0, sizeof(mark));
  memset(summark, 0, sizeof(summark));
  memset(F, 0, sizeof(F));
  memset(dp, 0, sizeof(dp));
  memset(sum, 0, sizeof(sum));
  for (auto p : ones) {
    mark[p.first]++;
    mark[p.second + 1]--;
  }
  for (int i = 1; i <= n + 1; ++i) {
    mark[i] += mark[i - 1];
  }
  for (int i = 1; i <= n; ++i) {
    summark[i] = (mark[i] ? 1 : 0) + summark[i - 1];
  }
  for (auto p : zeros) {
    if (summark[p.second] - summark[p.first - 1] == p.second - p.first + 1)
      return 0;
    F[p.second + 1] = max(p.first, F[p.second + 1]);
  }
  for (int i = 1; i <= n + 1; ++i) {
    F[i] = max(F[i], F[i - 1]);
  }
  dp[0] = 1;
  sum[0] = 1;
  return 1;
}
long long DP() {
  for (int i = 1; i <= n + 1; ++i) {
    if (mark[i]) {
      sum[i] = sum[i - 1];
      continue;
    }
    dp[i] = sum[i - 1] - (F[i] ? sum[F[i] - 1] : 0);
    dp[i] %= MOD;
    sum[i] = dp[i] + sum[i - 1];
    sum[i] %= MOD;
  }
  return dp[n + 1];
}
int main() {
  vector<pair<int, pair<int, int>>> v;
  int k, m;
  scanf("%d%d%d", &n, &k, &m);
  for (int i = 0; i < m; ++i) {
    int l, r, x;
    scanf("%d%d%d", &l, &r, &x);
    v.push_back({x, {l, r}});
  }
  long long ans = 1;
  for (int i = 0; i < k; ++i) {
    zeros.clear();
    ones.clear();
    for (auto p : v) {
      if (p.first & (1 << i)) {
        ones.push_back(p.second);
      } else
        zeros.push_back(p.second);
    }
    if (build()) {
      ans *= DP();
    } else {
      ans = 0;
    }
    ans %= MOD;
  }
  if (ans < 0) ans += MOD;
  printf("%I64lld\n", ans);
  return 0;
}
