F. 与运算区间

每个测试的时间限制：3 秒
内存限制：256 兆字节

给定三个整数 $n$、$k$、$m$ 以及 $m$ 个条件 $(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$。

请计算满足以下条件的、由 $n$ 个整数构成的不同数组 $a$ 的数量：

• 对于每个 $1 \le i \le n$，有 $0 \le a_i < 2^k$；
• 对于每个 $1 \le i \le m$，有 $a[l_i] \ \&\ a[l_i+1] \ \&\ \dots \ \&\ a[r_i] = x_i$（按位与）。

如果两个数组 $a$ 和 $b$ 存在某个位置 $i$ 使得 $a_i \neq b_i$，则认为它们不同。

答案可能很大，请输出它对 $998244353$ 取模的结果。

输入
第一行包含三个整数 $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$ 的长度、数值上限的指数（所有数小于 $2^k$）以及条件的个数。

接下来 $m$ 行，每行描述一个条件：$l_i$、$r_i$ 和 $x_i$（$1 \le l_i \le r_i \le n$，$0 \le x_i < 2^k$），即该条件涉及的区间端点以及要求的按位与结果。

输出
输出一个整数 —— 满足所有条件的数组 $a$ 的个数，对 $998244353$ 取模。

示例

输入

4 3 2  
1 3 3  
3 4 6  

输出

3  

输入

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

输出

33  

提示
可以回忆一下按位与运算的定义。

在第一个示例中，答案对应的数组为：$[3,3,7,6]$、$[3,7,7,6]$ 和 $[7,3,7,6]$。