G. XOR Segments
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One Day when Lskkkno1 was struggling with Codeforces, he met a question called 'AND Segments', he immediately worked out the question but only to find that he misunderstood the question. :D

Now Lskkkno1 is very annoying, so he wants you to solve the misunderstood question too!

Given three non-negative integers $$$n$$$, $$$k$$$, $$$m$$$, and $$$m$$$ restrictions $$$(l_1, r_1, x_1), (l_2, r_2, x_2), \cdots , (l_m, r_m, x_m)$$$.

Please calculate how many arrays of length $$$n$$$ satisfy the following requirements:

- for each $$$1 \leq i \leq n$$$, $$$0 \leq a_i \lt 2^k$$$.

- for each $$$1 \leq i \leq m$$$, $$$a_{l_i} \bigoplus a_{l_i + 1} \bigoplus \cdots \bigoplus a_{r_i} = x_i$$$.($$$\bigoplus$$$ is bitwise exclusive or operator)

Two arrays $$$a$$$, $$$b$$$ are different if and only if there exists a position $$$i$$$ that $$$a_i \neq b_i$$$.

For the answer may be very large,you should print the answer modulo $$$998244353$$$.

Input

The first line contains three integers $$$n$$$, $$$k$$$, $$$m$$$ — the length of array $$$a$$$ ,the elements in array $$$a$$$ should less than $$$2^k$$$, and the number of restrictions.

The next $$$m$$$ lines each contains three integers, $$$l_i, r_i, x_i$$$ describe a piece of restriction.

It's guaranteed that $$$1 \le n \le 10^6$$$, $$$0 \le m \le 10^6$$$, $$$0 \le k \le 31$$$, $$$1 \le l_i \le r_i \le n$$$, $$$x_i \lt 2^k$$$.

Output

Output a single integer — the number of arrays satisfying the requirements modulo $$$998244353$$$.

Examples
Input
2 1 0
Output
4
Input
3 1 1
1 3 0
Output
4
Input
2 0 1
1 2 0
Output
1
Note

In the first example, there are no restrictions, so the arrays are : $$$[0,0]$$$, $$$[0,1]$$$, $$$[1,0]$$$, $$$[1, 1]$$$.

In the second example, the four arrays are : $$$[0, 0, 0]$$$, $$$[0, 1, 1]$$$, $$$[1, 0, 1]$$$, $$$[1, 1, 0]$$$ which satisfy $$$a_1 \bigoplus a_2 \bigoplus a_3 = 0$$$.

In the third example, the only array is : $$$[0, 0]$$$, because $$$a_i$$$ must be less than $$$2^k$$$.