不能是区间最大值

时间限制：3s
空间限制：512MB

题目描述

求排列 $P=(P_1,P_2,\ldots,P_N)$ 的数量，使它同时满足给定的 $M$ 个条件。答案对 $998244353$ 取模。

第 $i$ 个条件给出 $L_i,R_i,X_i$，要求 $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$ 中的最大值不能是 $P_{X_i}$。

输入格式

第一行包含两个整数 $N,M$。

接下来 $M$ 行，每行包含三个整数 $L_i,R_i,X_i$。

输出格式

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

样例输入 1

3 2
1 3 2
1 2 1

样例输出 1

1

样例输入 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

数据范围

• $1\le N\le 500$；
• $1\le M\le 10^5$；
• $1\le L_i\le X_i\le R_i\le N$。