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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class C1327F {

    static int modulo = 998244353;

    public static void main(String[] args) {
        var scanner = new BufferedScanner();
        var writer = new PrintWriter(new BufferedOutputStream(System.out));

        var n = scanner.nextInt();
        var p2 = new int[n + 1];
        p2[0] = 1;
        for (int i = 1; i <= n; i++) {
            p2[i] = (int) (((long) p2[i - 1] << 1) % modulo);
        }
        var k = scanner.nextInt();
        var m = scanner.nextInt();
        var l = new int[m + 1];
        var r = new int[m + 1];
        var x = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            l[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
            x[i] = scanner.nextInt();
        }
        var ans = 1L;
        for (int bit = 0; bit < k; bit++) {
            var bitMask = 1 << bit;
            var oneRange = new int[n + 2];
//            var zeroOut = new HashMap<Integer, List<Integer>>();
            var maxIns = new int[n + 2];
            for (int j = 1; j <= m; j++) {
                if ((bitMask & x[j]) > 0) {
                    oneRange[l[j]]++;
                    oneRange[r[j] + 1]--;
                } else {
//                    zeroOut.putIfAbsent(r[j] + 1, new ArrayList<>());
//                    zeroOut.get(r[j] + 1).add(j);
                    maxIns[r[j] + 1] = Math.max(maxIns[r[j] + 1], l[j]);
                }
            }
            var f = new int[n + 2]; // f[i]=[1..i]以0结尾的总数，结果就是f[n+1]
            f[0] = 1;
            var sum = f[0];
            var prev = 0;
            var oneCount = 0;
            for (int i = 1; i <= n + 1; i++) {
//                var outs = zeroOut.get(i);
//                if (outs != null) {
//                    var maxIn = 0;
//                    for (var cond : outs) {
//                        maxIn = Math.max(maxIn, l[cond]);
//                    }
                    var maxIn = maxIns[i];
                    while (prev < maxIn) {
                        sum = (sum + modulo - f[prev]) % modulo;
                        prev++;
                    }
//                }
                oneCount += oneRange[i];
                if (oneCount > 0) {
                    f[i] = 0;
                } else {
                    f[i] = sum;
                    sum = (sum + f[i]) % modulo;
                }
            }
            ans = ans * f[n + 1] % modulo;
        }
        writer.println(ans);

        scanner.close();
        writer.flush();
        writer.close();
    }

    public static class BufferedScanner {
        BufferedReader br;
        StringTokenizer st;

        public BufferedScanner(Reader reader) {
            br = new BufferedReader(reader);
        }

        public BufferedScanner() {
            this(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

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

        void close() {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    static long gcd(long a, long b) {
        if (a < b) {
            return gcd(b, a);
        }
        while (b > 0) {
            long tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

    static long inverse(long a, long m) {
        long[] ans = extgcd(a, m);
        return ans[0] == 1 ? (ans[1] + m) % m : -1;
    }

    private static long[] extgcd(long a, long m) {
        if (m == 0) {
            return new long[]{a, 1, 0};
        } else {
            long[] ans = extgcd(m, a % m);
            long tmp = ans[1];
            ans[1] = ans[2];
            ans[2] = tmp;
            ans[2] -= ans[1] * (a / m);
            return ans;
        }
    }

    private static List<Integer> primes(double upperBound) {
        var limit = (int) Math.sqrt(upperBound);
        var isComposite = new boolean[limit + 1];
        var primes = new ArrayList<Integer>();
        for (int i = 2; i <= limit; i++) {
            if (isComposite[i]) {
                continue;
            }
            primes.add(i);
            int j = i + i;
            while (j <= limit) {
                isComposite[j] = true;
                j += i;
            }
        }
        return primes;
    }


}
