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].
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class ANDSegmentsREDO {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int M = sc.nextInt();
        Range[] ranges = new Range[M + 1];
        ranges[0] = new Range(0, 0, 0);
        for (int i = 1; i <= M; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int x = sc.nextInt();
            ranges[i] = new Range(l, r, x);
        }
        long ans = 1;
        for (int k = 0; k < K; k++) {
            int bit = 1 << k;
            // each spot is either a 1, 0, or inactive.
            /**
             * Actually, it's either 1, or (0/inactive), and those two act the same
             * for our purposes
             */
            int[] one = new int[N + 2];
            int[] active = new int[N + 2];

            int[] leftmostJumpFrom = new int[N + 2];
            // for each position, we need to know the range that ends
            // before our position that was a zero.
            // Our zero placement here means any interval overlapping here is safe.
            // However, the rightmost interval that is disjoint is NOT safe.
            // So, we can only build off of states that PLACED ZEROS in
            // rightmost[pos].l and onward. If we jumped off of some state earlier,
            // that rightmost interval would be unsatisfied.
            /**
             * KEY ERROR!
             * Although you try to keep sliding the pointer of the rightmost interval that
             * doesn't overlap with you, that isn't necessarily the MOST RESTRICTIVE
             * one in terms of where we could arrive from.
             * Consider:
             * If we sweep based on right endpoint, we'll end up having the left
             * minimum launchpoint become NOT-monotonic. Which is incorrect.
             *   [          ]
             *      [    ]
             */
            leftmostJumpFrom[0] = 0; // stores the leftmost position we can jump from,
            // without skipping over an entire interval
            // maintain the invariant
            for (int i = 0; i <= M; i++) {
                active[ranges[i].l]++;
                active[ranges[i].r + 1]--;
                if ((ranges[i].x & bit) == 0) {
                    // it's a forced zero, so add it
                    // if it's a one, our DP can never have anything there
                    leftmostJumpFrom[ranges[i].r + 1] = Math.max(leftmostJumpFrom[ranges[i].r + 1], ranges[i].l);
//                    System.out.println(ranges[i]);
                }
                else {
                    // ones supersede any zero ranges covering it
                    one[ranges[i].l]++;
                    one[ranges[i].r + 1]--;
                }
            }

            long[] dpZero = new long[N + 2];
            // dpZero[pos] = the number of ways we can satisfy all the segments
            // up until now, GIVEN THAT we placed a zero at pos
            long[] prefix = new long[N + 2];
            dpZero[0] = 1; // position 0 is always safe, base case
            prefix[0] = 1;

            for (int pos = 1; pos <= N + 1; pos++) {
                /**
                 * We can combine a lot of the precomputation to do it AS WE SWEEP,
                 * so that cuts out a factor of 3 or so
                 */
                one[pos] += one[pos - 1];
                active[pos] += active[pos - 1];

                // we can only transition to this state as a ZERO
                // if it is forced to be a zero, or it's unspecified
                leftmostJumpFrom[pos] = Math.max(leftmostJumpFrom[pos], leftmostJumpFrom[pos - 1]);
                // This is tricky, but we can know that all the 0-intervals have been marked during the process
                // above. Thus, during this sweep, we will always pass the r+1 point for each interval, telling
                // us a new interval that is part of our lower bound. So, all the positions relevant WILL receive
                // that information through this repeated maxing.
//                System.out.println("Pos " + pos + " one: " + one[pos] + " active: " + active[pos]);
                if (one[pos] <= 0) {
                    int minAllowed = leftmostJumpFrom[pos];
                    dpZero[pos] = prefix[pos - 1];
                    if (minAllowed > 0) {
                        dpZero[pos] -= prefix[minAllowed - 1];
                        if (dpZero[pos] < 0) {
                            dpZero[pos] += mod;
                        }
                    }
                }
                prefix[pos] = prefix[pos - 1] + dpZero[pos];
                if (prefix[pos] > mod) {
                    prefix[pos] -= mod;
                }

            }
            ans = (ans * dpZero[N + 1]) % mod;
        }
        out.println(ans);

        out.close();
    }

    static long mod = 998244353;

    static class Range implements Comparable<Range> {
        int l, r, x;
        public Range(int lo, int hi, int val) {
            l = lo; r = hi; x = val;
        }
        public int compareTo(Range r2) {
            // sort by lowest r, then by decreasing length (lowest l)
            return r - r2.r != 0 ? r - r2.r : l - r2.l;
        }
        public String toString() {
            return l + ", " + r + ": " + Integer.toBinaryString(x);
        }
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}