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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FANDSegments solver = new FANDSegments();
        solver.solve(1, in, out);
        out.close();
    }

    static class FANDSegments {
        int n;
        int m;
        int k;
        int[][] arr;
        int mod = 998244353;

        public void readInput(Scanner sc) {
            n = sc.nextInt();
            k = sc.nextInt();
            m = sc.nextInt();
            arr = new int[m][3];
            for (int i = 0; i < m; i++)
                for (int j = 0; j < 3; j++)
                    arr[i][j] = sc.nextInt();
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int q = 1;
            while (q-- > 0) {
                readInput(sc);
                long ans = 1;
                for (int i = 0; i < k; i++) {
                    ans *= calc(i);
                    ans %= mod;
                }
                pw.println(ans);
            }
        }

        private long calc(int bit) {
            int[] max = new int[n + 2];
            int[] ones = new int[n + 2];
            for (int i = 0; i < m; i++) {
                if ((arr[i][2] & 1 << bit) == 0) {
                    max[arr[i][1]] = Math.max(max[arr[i][1]], arr[i][0]);
                } else {
                    ones[arr[i][0]]++;
                    ones[arr[i][1] + 1]--;
                }
            }
            for (int i = 1; i <= n + 1; i++) {
                max[i] = Math.max(max[i - 1], max[i]);
                ones[i] += ones[i - 1];
            }
            long[] dp = new long[n + 2];
            long[] prefix = new long[n + 2];
            dp[0] = 1;
            prefix[0] = 1;
            for (int i = 1; i <= n + 1; i++) {
                if (ones[i] == 0) {
                    dp[i] = prefix[i - 1];
                    if (max[i - 1] - 1 >= 0)
                        dp[i] -= prefix[max[i - 1] - 1];
                    dp[i] = (dp[i] + mod) % mod;
                } else
                    dp[i] = 0;
                prefix[i] = prefix[i - 1] + dp[i];
                prefix[i] %= mod;
            }
            return dp[n + 1];
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

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

    }
}

