← 返回题目列表

AtCoder · abc262_h

Ex. 最大限制序列

中文机器翻译题面 查看原题

分数: 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