CF1327F 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$ 取模的结果。

在一个样例中，合法的序列 $a$ 有：$[3, 3, 7, 6]$，$[3, 7, 7, 6]$ 以及 $[7, 3, 7, 6]$。