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].
import sys
range = xrange
input = raw_input

MOD = 998244353 
def red(x):
    return x if x < MOD else x - MOD

inp = [int(x) for x in sys.stdin.read().split()]; ii = 0
n = inp[ii]; ii += 1
k = inp[ii]; ii += 1
m = inp[ii]; ii += 1

L = [x - 1 for x in inp[ii + 0: ii + 3 * m: 3]]
R = inp[ii + 1: ii + 3 * m: 3]
A = inp[ii + 2: ii + 3 * m: 3]

Lbuckets = [[] for _ in range(n + 1)]
Rbuckets = [[] for _ in range(n + 1)]
for i in range(m):
    Lbuckets[L[i]].append(i)
    Rbuckets[R[i]].append(i)

DP = [[0]*k for _ in range(n + 1)]
DP.append([1]*k)

Lind = [-1] * k
Rind = [0]  * k
marked = [1] * k
for i in range(n + 1):
    dp = DP[i]

    for ind in Lbuckets[i]:
        a = A[ind]
        r = R[ind]
        for j in range(k):
            if a & (1 << j) and Rind[j] < r:
                for x in range(Rind[j], r):
                    marked[j] = red(marked[j] + DP[x][j])
                Rind[j] = r
    for ind in Rbuckets[i]:
        a = A[ind]
        l = L[ind]
        for j in range(k):
            if not a & (1 << j) and Lind[j] < l:
                for x in range(Lind[j], l):
                    marked[j] = red(marked[j] - DP[x][j] + MOD)
                Lind[j] = l
    
    for j in range(k):
        if i == Rind[j]:
            dp[j] = marked[j]
            marked[j] = red(marked[j] + dp[j])
            Rind[j] += 1

prod = 1
for j in range(k):
    prod = prod * DP[n][j] % MOD

print prod
