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