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;
const int MOD = 998244353;
template <typename T>
struct modular {
  constexpr modular() : val(0) {}
  constexpr modular(const modular<T>& _m) : val(_m.val) {}
  template <typename U>
  constexpr modular(const U& _r = U()) {
    val = -MOD <= _r && _r < MOD ? _r : _r % MOD;
    if (val < 0) {
      val += MOD;
    }
  }
  const T operator()() { return val; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(val);
  }
  modular<T>& operator+=(const modular<T>& _m) {
    if ((val += _m.val) >= MOD) {
      val -= MOD;
    }
    return *this;
  }
  modular<T>& operator-=(const modular<T>& _m) {
    if ((val -= _m.val) < 0) {
      val += MOD;
    }
    return *this;
  }
  modular<T>& operator*=(const modular<T>& _m) {
    val = modular<T>(static_cast<int64_t>(val) * static_cast<int64_t>(_m.val))
              .val;
    return *this;
  }
  modular<T>& operator/=(const modular<T>& _m) {
    T a = _m.val, b = MOD, u = 0, v = 1;
    while (a != 0) {
      T q = b / a;
      b -= q * a;
      swap(a, b);
      u -= q * v;
      swap(u, v);
    }
    return *this *= u;
  }
  modular<T>& operator=(const modular<T>& _m) {
    val = _m.val;
    return *this;
  }
  template <typename U>
  modular<T>& operator+=(const U& _r) {
    return *this += modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator-=(const U& _r) {
    return *this -= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator*=(const U& _r) {
    return *this *= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator/=(const U& _r) {
    return *this /= modular<T>(_r);
  }
  template <typename U>
  modular<T>& operator=(const U& _r) {
    val = modular<T>(_r).val;
    return *this;
  }
  modular<T> operator-() { return modular<T>(-val); }
  template <typename U>
  friend bool operator==(const modular<U>&, const modular<U>&);
  friend std::istream& operator>>(std::istream& os, modular<T>& _m) {
    os >> _m.val;
    _m *= 1;
    return os;
  }
  friend std::ostream& operator<<(std::ostream& os, const modular<T>& _m) {
    return os << _m.val;
  }
  template <typename U>
  modular<T> exp(U e) {
    modular<T> res = 1;
    modular<T> b = val;
    if (e < 0) {
      b = 1 / b;
      e *= -1;
    }
    for (; e; e >>= 1) {
      if (e & 1) {
        res *= b;
      }
      b *= b;
    }
    return res;
  }

 private:
  T val;
};
template <typename T>
inline modular<T> operator+(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T, typename U>
inline modular<T> operator+(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) += _rhs;
}
template <typename T>
inline modular<T> operator-(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T, typename U>
inline modular<T> operator-(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) -= _rhs;
}
template <typename T>
inline modular<T> operator*(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T, typename U>
inline modular<T> operator*(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) *= _rhs;
}
template <typename T>
inline modular<T> operator/(const modular<T>& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const modular<T>& _lhs, const U& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T, typename U>
inline modular<T> operator/(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) /= _rhs;
}
template <typename T>
inline bool operator==(const modular<T>& _lhs, const modular<T>& _rhs) {
  return _lhs.val == _rhs.val;
}
template <typename T, typename U>
inline bool operator==(const modular<T>& _lhs, const U& _rhs) {
  return _lhs == modular<T>(_rhs);
}
template <typename T, typename U>
inline bool operator==(const U& _lhs, const modular<T>& _rhs) {
  return modular<T>(_lhs) == _rhs;
}
template <typename T>
inline bool operator!=(const modular<T>& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const modular<T>& _lhs, const U& _rhs) {
  return !(_lhs == _rhs);
}
template <typename T, typename U>
inline bool operator!=(const U& _lhs, const modular<T>& _rhs) {
  return !(_lhs == _rhs);
}
void solve() {
  int n, L, m;
  cin >> n >> L >> m;
  vector<tuple<int, int, int>> a(m);
  for (auto& _ : a) {
    int x, y, z;
    cin >> x >> y >> z;
    y++;
    _ = {x, y, z};
  }
  modular<int> res = 1;
  for (int k = 0; k < L; k++) {
    vector<int> trk(n + 2);
    vector<int> left(n + 2, 0);
    for (auto& _ : a) {
      int x, y, z;
      tie(x, y, z) = _;
      if (z >> k & 1) {
        trk[x]++;
        trk[y]--;
      } else {
        left[y] = max(left[y], x);
      }
    }
    for (int i = 0; i <= n; i++) {
      trk[i + 1] += trk[i];
      left[i + 1] = max(left[i + 1], left[i]);
    }
    vector<modular<int>> dp(n + 2), sum(n + 3);
    dp[0] = sum[1] = 1;
    for (int i = 1; i <= n + 1; i++) {
      if (!trk[i]) {
        int l = left[i];
        dp[i] = sum[i] - sum[l];
      }
      sum[i + 1] = sum[i] + dp[i];
    }
    res *= dp[n + 1];
  }
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}
