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 java.util.*;
     
    public class Main{
     
        public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            long ans=1,mod=998244353;
            int n=sc.nextInt(),k=sc.nextInt(),m=sc.nextInt();
            int l[]=new int[m+1],r[]=new int[m+1],c[]=new int[m+1];
            for(int i=1;i<=m;i++){
                l[i]=sc.nextInt();
                r[i]=sc.nextInt();
                c[i]=sc.nextInt();
            }
            
            for(int i=0;i<k;i++){
                int bit[]=new int[n+2],lm[]=new int[n+2];
                long dp[]=new long[n+2];
                for(int j=1;j<=m;j++){
                    if((c[j]&1<<i)!=0){
                        bit[l[j]]++;
                        bit[r[j]+1]--;
                    }else{
                        lm[r[j]+1]=Math.max(lm[r[j]+1],l[j]);
                    }
                }
                dp[0]=1;
                
                for(int j=1;j<=n+1;j++){
                    bit[j]+=bit[j-1];
                    lm[j]=Math.max(lm[j-1],lm[j]);
                    long res=0;
                    if(bit[j]==0){
                        res=dp[j-1];
                        if(lm[j]!=0){
                            res=(res-dp[lm[j]-1]+mod)%mod;
                        }
                    }
                    dp[j]=(mod+(dp[j-1]+res)%mod)%mod;
                    if(j==n+1){
                        ans=(mod+(ans*res)%mod)%mod;
                    }
                }
                
            }
            
            
            System.out.println(ans);
        }
        
    }