分数: 600 点
问题陈述
求模数 998244353,整数序列 A = (A_1, \dots, A_N) 长度 N 满足以下所有条件:
- 0 \leq A_i \leq M 对于所有人 i 这样 1 \leq i \leq N.
- 的最大值 A_{L_j}, \dots, A_{R_j} is X_j 对于所有人 j 这样 1 \leq j \leq Q.
约束
- 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
输出
打印答案。
示例输入 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