← 返回题目列表

AtCoder · arc183_c

C. 不是 Argmax

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

分数: 600 点

问题陈述

求模数 998244353,排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) 满足以下所有条件 M 条件。

  • 的 i-第条件:其中的最大值 P_{L_i},P_{L_i+1},\cdots,P_{R_i} is 不 P_{X_i}。 在这里, L_i, R_i,和 X_i 是输入中给出的整数。

约束

  • 1 \leq N \leq 500
  • 1 \leq M \leq 10^5
  • 1 \leq L_i \leq X_i \leq R_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_M R_M X_M

输出

打印答案。


示例输入 1

3 2
1 3 2
1 2 1

示例输出 1

1

只有一种排列, P=(1,2,3),满足条件。


示例输入 2

5 1
1 1 1

示例输出 2

0

示例输入 3

10 5
3 8 4
3 10 4
1 7 2
1 8 3
3 8 7

示例输出 3

1598400

示例输入 4

15 17
2 11 9
2 15 13
1 14 2
5 11 5
3 15 11
1 6 2
4 15 12
3 11 6
9 13 10
2 14 6
10 15 11
1 8 6
6 14 8
2 10 2
6 12 6
3 14 12
2 6 2

示例输出 4

921467228