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;
template <class n, class second>
ostream &operator<<(ostream &p, pair<n, second> x) {
  return p << "<" << x.first << ", " << x.second << ">";
}
template <class n>
auto operator<<(ostream &p, n y) ->
    typename enable_if<!is_same<n, string>::value,
                       decltype(y.begin(), p)>::type {
  int o = 0;
  p << "{";
  for (auto c : y) {
    if (o++) p << ", ";
    p << c;
  }
  return p << "}";
}
void dor() { cerr << '\n'; }
template <class n, class... second>
void dor(n p, second... y) {
  cerr << p << " ";
  dor(y...);
}
template <class n, class second>
void mini(n &p, second y) {
  if (p > y) p = y;
}
template <class n, class second>
void maxi(n &p, second y) {
  if (p < y) p = y;
}
const int MXN = 5e5 + 5;
int bits[32][MXN];
vector<pair<int, int> > segs[32];
int nr[MXN];
int mod = 998244353;
long long ways[MXN];
long long sum_way[MXN];
int sum_ways(int a, int b) {
  if (a == 0) return sum_way[b];
  int res = sum_way[b] - sum_way[a - 1];
  if (res < 0) res += mod;
  return res;
}
void solve() {
  int n, k, m;
  scanf("%d%d%d", &n, &k, &m);
  for (int i = (1); i <= (int)(m); ++i) {
    int a, b, x;
    scanf("%d%d%d", &a, &b, &x);
    for (int j = 0; j < (int)(k); ++j) {
      if ((x & (1 << j)) == 0) {
        segs[j].push_back({a, b});
      } else {
        bits[j][a]++;
        bits[j][b + 1]--;
      }
    }
  }
  long long all_res = 1;
  for (int j = 0; j < (int)(k); ++j) {
    for (int i = (1); i <= (int)(n); ++i) bits[j][i] += bits[j][i - 1];
    nr[0] = 0;
    for (int i = (1); i <= (int)(n); ++i) {
      if (bits[j][i])
        nr[i] = nr[i - 1];
      else {
        nr[i] = nr[i - 1] + 1;
      }
    }
    for (auto &i : segs[j]) {
      if (bits[j][i.first]) {
        i.first = nr[i.first];
        i.first++;
      } else {
        i.first = nr[i.first];
      }
      i.second = nr[i.second];
      if (i.first > i.second) {
        ;
        all_res = 0;
        continue;
      }
    };
    for (int i = (1); i <= (int)(n); ++i)
      ;
    ;
    sort((segs[j]).begin(), (segs[j]).end(),
         [&](pair<int, int> a, pair<int, int> b) {
           return a.second < b.second;
         });
    reverse((segs[j]).begin(), (segs[j]).end());
    int left_wsk = 0;
    ways[0] = 1;
    sum_way[0] = 1;
    for (int i = (1); i <= (int)(nr[n]); ++i) {
      while (segs[j].size() && segs[j].back().second < i) {
        maxi(left_wsk, segs[j].back().first);
        segs[j].pop_back();
      };
      ways[i] = sum_ways(left_wsk, i - 1);
      sum_way[i] = sum_way[i - 1] + ways[i];
      if (sum_way[i] >= mod) sum_way[i] -= mod;
    }
    while (segs[j].size()) {
      maxi(left_wsk, segs[j].back().first);
      segs[j].pop_back();
    };
    all_res *= sum_ways(left_wsk, nr[n]);
    all_res %= mod;
  }
  if (all_res < 0) all_res += mod;
  printf("%lld\n", all_res);
}
int main() { solve(); }
