CF1327F.AND Segments

You are given three integers $n$ , $k$ , $m$ and $m$ conditions $(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$ .

Calculate the number of distinct arrays $a$ , consisting of $n$ integers such that:

• $0 \le a_i < 2^k$ for each $1 \le i \le n$ ;
• bitwise AND of numbers $a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$ for each $1 \le i \le m$ .

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

The number can be pretty large so print it modulo $998244353$ .

The first line contains three integers $n$ , $k$ and $m$ ( $1 \le n \le 5 \cdot 10^5$ , $1 \le k \le 30$ , $0 \le m \le 5 \cdot 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 \le l_i \le r_i \le n$ , $0 \le x_i < 2^k$ ) — the borders of the condition segment and the required bitwise AND value on it.

Print a single integer — the number of distinct arrays $a$ that satisfy all the above conditions modulo $998244353$ .

You can recall what is a bitwise AND operation here.

In the first example, the answer is the following arrays: $[3, 3, 7, 6]$ , $[3, 7, 7, 6]$ and $[7, 3, 7, 6]$ .