题目描述

给定一个 $(1,2,\cdots,N)$ 的排列 $P=(P_1,P_2,\cdots,P_N)$，请计算满足以下 $M$ 个条件的排列数量，并将答案对 $998244353$ 取模。

• 第 $i$ 个条件：在 $P_{L_i},P_{L_i+1},\cdots,P_{R_i}$ 这一段中，最大值不是 $P_{X_i}$。其中，$L_i,R_i,X_i$ 是输入给定的整数。

输入格式

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

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

输出格式

请输出满足条件的排列数量，对 $998244353$ 取模后的结果。

样例 1

输入

3 2
1 3 2
1 2 1

输出

1

样例 2

输入

5 1
1 1 1

输出

0

样例 3

输入

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

输出

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

输出

921467228

说明/提示

限制

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

样例解释 1

满足条件的只有 $P=(1,2,3)$ 这一种情况。

由 ChatGPT 4.1 翻译