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].
/*
 ID: tommatt1
 LANG: JAVA
 TASK: 
*/
import java.util.*;
import java.io.*;
public class cf1327f{

	public static void main(String[] args)throws IOException {
		//BufferedReader bf=new BufferedReader(new FileReader("cf1327f.in"));
		//PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("cf1327f.out")));
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		int n=Integer.parseInt(st.nextToken());
		int k=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		int[] la=new int[m];
		int[] ra=new int[m];
		int[] v=new int[m];
		long ans=1;
		long mod=998244353;
		for(int i=0;i<m;i++) {
			st=new StringTokenizer(bf.readLine());
			la[i]=Integer.parseInt(st.nextToken());
			ra[i]=Integer.parseInt(st.nextToken());
			v[i]=Integer.parseInt(st.nextToken());
		}
		for(int b=0;b<k;b++) {
			int[] one=new int[n+2];
			int[] l=new int[n+2];
			for(int i=0;i<m;i++) {
				if((v[i]&(1<<b))>0) {
				one[la[i]]++;
				one[ra[i]+1]--;
				}
				else {
					l[ra[i]+1]=Math.max(la[i], l[ra[i]+1]);
				}
			}
			for(int i=1;i<=n+1;i++) {
				l[i]=Math.max(l[i-1], l[i]);
				one[i]+=one[i-1];
			}
			long[] dp=new long[n+2];
			dp[0]=1;
			for(int i=1;i<=n+1;i++) {
				long tmp=0;
				if(one[i]==0) {
					tmp=dp[i-1];
					if(l[i]>0) {
						tmp=(tmp-dp[l[i]-1])%mod;
					}
				}
				else {
					tmp=0;
				}
				if(i==n+1) {
					ans=(ans*tmp)%mod;
					if(ans<0) ans+=mod;
					break;
				}
				dp[i]=(dp[i-1]+tmp)%mod;
			}
		}
		out.println(ans);
		out.close();
	}

}


