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.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FANDSegments solver = new FANDSegments();
        solver.solve(1, in, out);
        out.close();
    }

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

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            n = in.scanInt();
            k = in.scanInt();
            m = in.scanInt();
            query = new int[m][3];
            for (int[] pair : query) {
                pair[0] = in.scanInt();
                pair[1] = in.scanInt();
                pair[2] = in.scanInt();
            }
            long ans = 1;
            for (int i = 0; i <= k - 1; i++) ans = (ans * calc(i)) % mod;
            out.println(ans);

        }

        private int calc(int i) {
            int[] one = new int[n + 2];
            int[] max = new int[n + 2];
            for (int[] pair : query) {
                if (((pair[2] >> i) & 1) == 1) {
                    one[pair[0]]++;
                    one[pair[1] + 1]--;
                } else max[pair[1]] = Math.max(max[pair[1]], pair[0]);

            }
            int[] way = new int[n + 2];
            int[] sum = new int[n + 2];
            sum[0] = way[0] = 1;
            for (int j = 1; j <= n; j++) {
                one[j] += one[j - 1];
                if (one[j] == 0) {
                    if (max[j - 1] == 0) {
                        way[j] = sum[j - 1];
                    } else {
                        way[j] = (sum[j - 1] - sum[max[j - 1] - 1]);
                        if (way[j] < 0) way[j] += mod;
                    }
                }
                max[j] = Math.max(max[j - 1], max[j]);
                sum[j] = (sum[j - 1] + way[j]);
                if (sum[j] >= mod) sum[j] -= mod;
            }
            return (sum[n] + (max[n] == 0 ? 0 : -sum[max[n] - 1]) + mod) % mod;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

