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 <int m>
struct modint {
  unsigned x;
  modint() : x(0) {}
  modint(long long arg) {
    arg %= m;
    if (arg < 0) {
      x = arg + m;
    } else {
      x = arg;
    }
  }
  modint& operator+=(const modint& other) {
    x += other.x;
    if (x >= m) {
      x -= m;
    }
    return *this;
  }
  modint& operator*=(const modint& other) {
    x = (x * 1ull * other.x) % m;
    return *this;
  }
  modint& operator-=(const modint& other) {
    x += m - other.x;
    if (x >= m) {
      x -= m;
    }
    return *this;
  }
  modint operator+(const modint& other) const {
    modint tmp = *this;
    tmp += other;
    return tmp;
  }
  modint operator-(const modint& other) const {
    modint tmp = *this;
    tmp -= other;
    return tmp;
  }
  modint operator*(const modint& other) const {
    modint tmp = *this;
    tmp *= other;
    return tmp;
  }
  explicit operator int() const { return x; }
  modint& operator++() {
    ++x;
    if (x == m) {
      x = 0;
    }
    return *this;
  }
  modint& operator--() {
    if (x == 0) {
      x = m - 1;
    } else {
      --x;
    }
    return *this;
  }
  modint operator++(int) {
    modint tmp = *this;
    ++*this;
    return tmp;
  }
  modint operator--(int) {
    modint tmp = *this;
    --*this;
    return tmp;
  }
  bool operator==(const modint& other) const { return x == other.x; }
  bool operator!=(const modint& other) const { return x != other.x; }
  template <class T>
  modint operator^(T arg) const {
    if (arg == 0) {
      return 1;
    }
    if (arg == 1) {
      return x;
    }
    auto t = *this ^ (arg >> 1);
    t *= t;
    if (arg & 1) {
      t *= *this;
    }
    return t;
  }
  template <class T>
  modint operator^=(T arg) {
    return *this = *this ^ arg;
  }
  modint inv() const { return *this ^ (m - 2); }
};
const int MOD = 998244353;
struct cond {
  int l, r, x;
  bool operator<(const cond& b) const { return tie(l, r) < tie(b.l, b.r); }
};
int n, k, m;
cond a[500005];
int z[500005], id[500005];
modint<MOD> dp[500005], zz[500005];
int ric[500005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  cerr.tie(nullptr);
  cin >> n >> k >> m;
  for (int i = 0; i < m; i++) {
    cin >> a[i].l >> a[i].r >> a[i].x;
    a[i].l--;
  }
  sort(a, a + m);
  modint<MOD> p = 1;
  for (int b = 0; b < k; b++) {
    memset(z, 0, sizeof z);
    memset(zz, 0, sizeof zz);
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < m; i++) {
      if (a[i].x & (1 << b)) {
        z[a[i].l]++;
        z[a[i].r]--;
      }
    }
    for (int i = 1; i <= n; i++) z[i] += z[i - 1];
    for (int i = 0, cnt = 0; i <= n; i++) {
      id[i] = cnt;
      cnt += z[i] == 0;
    }
    vector<pair<int, int>> v;
    for (int i = 0; i < m; i++) {
      if (!(a[i].x & (1 << b))) {
        int lx = id[a[i].l] + 1;
        int rx = id[a[i].r];
        while (v.size() && v.back().first <= lx && rx <= v.back().second)
          v.pop_back();
        v.emplace_back(lx, rx);
      }
    }
    int f = id[n];
    f++;
    v.emplace_back(f, f);
    dp[0] = 1;
    zz[1] = 1;
    int lll = 0, id = 0;
    for (int x = 1; x <= f; x++) {
      while (id < (int)v.size() && v[id].second < x) {
        lll = max(lll, v[id].first);
        id++;
      }
      dp[x] = zz[x] - zz[lll];
      zz[x + 1] = zz[x] + dp[x];
    }
    p *= dp[f];
  }
  cout << (int)p << '\n';
}
