题目描述

找到长度为 $N$ 的整数序列 $A = (A_1, \ldots, A_N)$ 的数量，对 $998244353$ 取模，满足以下所有条件：

• 对于所有满足 $1 \leq i \leq N$ 的 $i$，有 $0 \leq A_i \leq M$。
• 对于所有满足 $1 \leq j \leq Q$ 的 $j$，有 $A_{L_j}, \ldots, A_{R_j}$ 中的最大值为 $X_j$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \lt 998244353$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N \quad (1 \leq i \leq Q)$
• $1 \leq X_i \leq M \quad (1 \leq i \leq Q)$
• 输入中的所有值都是整数。

输入格式

输入以标准输入给出，格式如下：

$N$ $M$ $Q$
$L_1 \ R_1 \ X_1$
$\vdots$
$L_Q \ R_Q \ X_Q$

输出格式

打印答案。

示例输入 1

3 3 2
1 2 2
2 3 3

示例输出 1

5

满足条件的序列有 $A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3)$。

示例输入 2

1 1 1
1 1 1

示例输出 2

1

示例输入 3

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

示例输出 3

135282163