蓝
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小柒作为某个学校的年级主任，对新招收的学生实行民主政策。
\hspace{15pt}今年一共招收了 m 名学生，编号从 1 到 m。每人要在编号从 1 到 n 的班级里挑一个加入。但是小柒做了 k 个限制，每个限制的格式由一个三元组 (l,r,c) 表示：
\hspace{23pt}\bullet\,当 c=0，代表编号在 [l,r] 的班级中，至少有一个班级为空。
\hspace{23pt}\bullet\,当 c=1，代表编号在 [l,r] 的班级中，至少有一个班级非空。
\hspace{15pt}小柒想知道在此限制的情况下，学生一共会有多少种不同的选班级的方案。由于答案可能很大，请将答案对 998\,244\,353 取模后输出。
\hspace{15pt}两个选班方案不同，当且仅当存在某个学生在两个方案中加入的班级不同。

输入描述:

\hspace{15pt}第一行输入三个整数 m,n,k\left(1\leq m \leq 10^9;\,1\leq n \leq 5 \times 10^3;\,1\leq k \leq 2\times 10^5\right)，表示学生的人数、班级的数量、限制的个数。
\hspace{15pt}此后 k 行，第 i 行输入三个整数 l_i,r_i,c_i\left(0\leq c_i \leq 1;\,1\leq l_i \leq r_i \leq n\right)，表示第 i 个限制。

输出描述:

\hspace{15pt}输出一个整数，代表所有合法的方案数对 998\,244\,353 取模后的结果。
示例1

输入

复制 
2 3 2
1 1 0
2 2 1

输出

复制 
3

说明

\hspace{15pt}在这个样例中，编号 1,2 的学生，要从编号 1,2,3 的班级中选一个加入，且需要满足：
\hspace{23pt}\bullet\,第一个班级必须为空，不能选；
\hspace{23pt}\bullet\,第二个班级必须非空，所以至少要有一个人加入；
\hspace{23pt}\bullet\,第三个班级没做限制，空不空都行。

\hspace{15pt}因此，一共有三种合法的选法：
\hspace{23pt}\bullet\,\{ \}、\{1,2\}、\{ \}；
\hspace{23pt}\bullet\,\{ \}、\{1\}、\{2 \}；
\hspace{23pt}\bullet\,\{ \}、\{2\}、\{1 \}。
示例2

输入

复制 
10000 15 15
1 8 1
1 8 0
2 5 1
3 7 0
8 8 0
5 5 1
3 8 0
6 7 1
8 15 1
15 15 0
13 15 1
10 15 0
1 15 1
1 15 0
8 9 1

输出

复制 
174100347