按位与区间

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定 $n,k,m$ 以及 $m$ 个限制 $(l_i,r_i,x_i)$。求长度为 $n$ 的整数序列 $a$ 的数量，使得：

• $0\le a_j<2^k$；
• 对每个限制，$a_{l_i}\mathbin{\&}a_{l_i+1}\mathbin{\&}\cdots\mathbin{\&}a_{r_i}=x_i$。

答案对 $998244353$ 取模。

输入格式

第一行三个整数 $n,k,m$。

接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$。

输出格式

输出满足条件的序列数量对 $998244353$ 取模后的结果。

样例输入 1

4 3 2
1 3 3
3 4 6

样例输出 1

3

样例输入 2

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

样例输出 2

33

数据范围

对于所有数据，$1\le n\le500000$，$1\le k\le30$，$0\le m\le500000$，$1\le l_i\le r_i\le n$，$0\le x_i<2^k$。