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].
// add in left sorted list and int[] condition for "bitmask" to add to and remove from every time a condition is found/passed
// dp is simply going back to the leftmost condition that has been passed and adding all dp (where 0 was in that idx in such
// a way that all prior conditions were satisfied) and make sure to keep track of prefixSums in another long[][]

// go bit by bit -- final result for each bit is adding all dp's from the left bound of farthest right 0-condition to end (if there are none, then use 1)
// then multiply sums for each of K bits

import java.util.*;
import java.io.*;

public class ANDSegments {
	static long MOD = 998244353;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		Triple[] conditionsLeft = new Triple[M];
		Triple[] conditionsRight = new Triple[M];
		for(int i = 0; i < M; ++i) {
			st = new StringTokenizer(in.readLine());
			Triple trip = new Triple(Integer.parseInt(st.nextToken()) - 1,
					Integer.parseInt(st.nextToken()) - 1,
					Long.parseLong(st.nextToken()));
			conditionsLeft[i] = conditionsRight[i] = trip;
		}
		Arrays.sort(conditionsLeft, new Comparator<Triple>() {
			public int compare(Triple t1, Triple t2) {
				return t1.l - t2.l;
			}
		});
		Arrays.sort(conditionsRight, new Comparator<Triple>() {
			public int compare(Triple t1, Triple t2) {
				return t1.r - t2.r;
			}
		});
		long ans = 1;
		for(int i = 0; i < K; ++i) {
			long[] dp = new long[N + 1];
			long[] prefixSum = new long[N + 1];
			int bits = 0;
			int conditionsRightIdx = -1;
			int conditionsLeftIdx = -1;
			int lastPassedLeft = -1;
			for(int j = 0; j <= N; ++j) {
				while(conditionsRightIdx + 1 < M && j > conditionsRight[conditionsRightIdx + 1].r) {
					conditionsRightIdx++;
					if((conditionsRight[conditionsRightIdx].x & ((long)1 << i)) > 0) {
						bits--;
					} else {
						lastPassedLeft = Math.max(lastPassedLeft, conditionsRight[conditionsRightIdx].l);
					}
				}
				while(conditionsLeftIdx + 1 < M && j >= conditionsLeft[conditionsLeftIdx + 1].l) {
					conditionsLeftIdx++;
					if((conditionsLeft[conditionsLeftIdx].x & ((long)1 << i)) > 0) {
						bits++;
					}
				}
				if(bits == 0) {
					if(j == 0) {
						dp[j] = 1;
					} else if(lastPassedLeft == -1) {
						dp[j] = (prefixSum[j - 1] + 1) % MOD;
					} else {
						dp[j] = (prefixSum[j - 1] - (lastPassedLeft > 0 ? prefixSum[lastPassedLeft - 1] : 0) + MOD) % MOD;
					}
				}
				prefixSum[j] = ((j > 0 ? prefixSum[j - 1] : 0) + dp[j]) % MOD;
			}
			ans = (ans * dp[N]) % MOD;
		}
		out.println(ans);
		in.close();
		out.close();
	}
	static class Triple {
		int l, r;
		long x;
		public Triple(int a, int b, long c) {
			l = a;
			r = b;
			x = c;
		}
	}
}