当前没有测试数据。

Ex - 最大有限序列

分值：$600$ 点

问题描述

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

• 对于所有 $i$，满足 $1 \leq i \leq N$，有 $0 \leq A_i \leq M$。
• 对于所有 $j$，满足 $1 \leq j \leq Q$，有 $A_{L_j}, \dots, 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 \, (1 \leq i \leq Q)$
• $1 \leq X_i \leq M \, (1 \leq i \leq Q)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $Q$

$L_1$ $R_1$ $X_1$

$\vdots$

$L_Q$ $R_Q$ $X_Q$

输出

输出答案。

3 3 2
1 2 2
2 3 3

5

$A = (0, 2, 3), (1, 2, 3), (2, 0, 3), (2, 1, 3), (2, 2, 3)$ 满足条件。

1 1 1
1 1 1

1

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

135282163