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.io.*;
import java.util.*;

/*
Прокрастинирую
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int INF = (int) (1e9 + 10);
    static final int MOD = (int) (998244353);
    static final int N = (int) (1e5 + 5);
    static final int LOGN = 30;

    static class Cond {
        int l, r, x;

        Cond(int l, int r, int x) {
            this.l = l;
            this.r = r;
            this.x = x;
        }
    }

    static long norm(long a) {
        a %= MOD;
        if (a < 0) a += MOD;
        return a;
    }

    static void solve() {
        int n = in.nextInt();
        int k = in.nextInt();
        int m = in.nextInt();

        Cond[] conds = new Cond[m];
        for (int i = 0; i < m; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            int x = in.nextInt();
            conds[i] = new Cond(l, r, x);
        }

        long ans = 1;
        for (int kk = 0; kk < k; kk++) {
            int[] ones = new int[n + 2];
            int[] right = new int[n + 2];
            for (int i = 0; i < m; i++) {
                if ((conds[i].x & (1 << kk)) != 0) {
                    ones[conds[i].l]++;
                    ones[conds[i].r + 1]--;
                } else {
                    right[conds[i].r] = Math.max(right[conds[i].r], conds[i].l);
                }
            }

            long[] dp = new long[n + 2];
            long[] prefSum = new long[n + 2];
            dp[0] = prefSum[0] = 1;
            int cnt1 = 0, maxr = 0;
            for (int i = 1; i <= n + 1; i++) {
                cnt1 += ones[i];
                if (cnt1 == 0) {
                    dp[i] = norm(prefSum[i - 1] - (maxr == 0 ? 0 : prefSum[maxr - 1]));
                }
                prefSum[i] = norm(prefSum[i - 1] + dp[i]);
                maxr = Math.max(maxr, right[i]);
            }

            ans = norm(ans * dp[n + 1]);
        }

        out.println(ans);
    }

    public static void main(String[] args) throws FileNotFoundException {
        in = new FastReader(System.in);
//        in = new FastReader(new FileInputStream("connect.in"));
        out = new PrintWriter(System.out);
//        out = new PrintWriter(new FileOutputStream("connect.out"));


        int q = 1;
//        q = in.nextInt();

        while (q-- > 0) {
            solve();
        }

        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        Integer nextInt() {
            return Integer.parseInt(next());
        }

        Long nextLong() {
            return Long.parseLong(next());
        }

        Double nextDouble() {
            return Double.parseDouble(next());
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}