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;
long long mod = (998244353LL);
inline long long poww(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
inline pair<long long, long long> operator+(pair<long long, long long> A,
                                            pair<long long, long long> B) {
  return pair<long long, long long>(A.first + B.first, A.second + B.second);
}
inline pair<long long, long long> operator-(pair<long long, long long> A,
                                            pair<long long, long long> B) {
  return pair<long long, long long>(A.first - B.first, A.second - B.second);
}
inline long long mult(long long a, long long b) { return (a * b) % mod; }
long long gcd(long long a, long long b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
long long n, m, q, k, v[500050], ans, dp[500050], opt[500050];
long long sum[500050];
long long l[500050], r[500050], x[500050], pref[500050];
pair<long long, long long> TT, w[500050];
string second;
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k >> q;
  for (long long i = 1; i <= q; i++) cin >> l[i] >> r[i] >> x[i];
  long long ans = 1LL;
  for (long long j = 0; j < k; j++) {
    vector<long long> en(n + 2);
    for (long long i = 0; i <= n + 1; i++) {
      pref[i] = dp[i] = sum[i] = 0;
      opt[i] = v[i] = 0;
    }
    for (long long i = 1; i <= q; i++) {
      if (x[i] & (1LL << j)) {
        pref[l[i]]++;
        pref[r[i] + 1]--;
        continue;
      }
      opt[r[i]] = max(opt[r[i]], l[i]);
    }
    long long cara = 0;
    for (long long i = 1; i <= n + 1; i++) {
      pref[i] += pref[i - 1];
      en[i] = cara;
      if (opt[i] > 0) cara = max(opt[i], cara);
    }
    dp[0] = 1;
    sum[0] = 1;
    for (long long i = 1; i <= n + 1; i++) {
      if (!pref[i]) {
        long long t = en[i];
        if (t > 0)
          dp[i] = sum[i - 1] - sum[t - 1];
        else
          dp[i] = sum[i - 1];
      }
      dp[i] %= mod;
      if (dp[i] < 0) dp[i] += mod;
      sum[i] = sum[i - 1] + dp[i];
      sum[i] %= mod;
    }
    ans *= dp[n + 1];
    ans %= mod;
    en.clear();
  }
  cout << ans << "\n";
}
