AND Segments

## 题目描述 你有三个整数 $n, k, m$ 以及 $m$ 个限制 $(l_1, r_1, x_1), (l_2, r_2, x_2), \ldots, (l_m, r_m, x_m)$。 计算满足下列条件的，长度为 $n$ 的序列 $a$ 的个数： - 对于每个 $1 \le i \le n$，$0 \le a_i \lt 2 ^ k$。 - 对于每个 $1 \le i \le m$，数字的按位与 $a[l_i] \text{ and } a_[l_i + 1] \text{ and } \ldots \text{ and } a[r_i] = x_i$。 两个序列 $a, b$ 被认为是不同的，当且仅当存在一个位置 $i$ 满足 $a_i \neq b_i$。 由于答案可能过大，请输出其对 $998\ 244\ 353$ 取模的结果。 ## 输入格式 第一行输入三个整数 $n, k, m ~(1 \le n \le 5 \cdot 10 ^ 5; 1 \le k \le 30; 0 \le m \le 5 \cdot 10 ^ 5)~$，分别表示数组 $a$ 的长度，$a$ 中元素的值域，以及限制的个数。 接下来 $m$ 行，每行描述一个限制 $l_i, r_i, x_i ~ (1 \le l_i \le r_i \le n; 0 \le x_i \lt 2 ^ k)$，分别表示限制的线段区间以及按位与值。 ## 输出格式 输出一行一个整数，表示满足条件的序列 $a$ 的个数，对 $998\ 244\ 353$ 取模的结果。 ### 说明/提示 你可以在 [这里](https://en.wikipedia.org/wiki/Bitwise_operation#AND) 获得有关按位与的信息。 在一个样例中，合法的序列 $a$ 有：$[3, 3, 7, 6]$，$[3, 7, 7, 6]$ 以及 $[7, 3, 7, 6]$。

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 $ .

4 3 2
1 3 3
3 4 6

3

5 2 3
1 3 2
2 5 0
3 3 3

33

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] $ .