C - Not Argmax Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

(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 は入力で与えられる整数である．

制約

  • 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) の 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

Score : 600 points

Problem Statement

Find the number, modulo 998244353, of permutations P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) that satisfy all of the following M conditions.

  • The i-th condition: The maximum among P_{L_i},P_{L_i+1},\cdots,P_{R_i} is not P_{X_i}. Here, L_i, R_i, and X_i are integers given in the input.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq M \leq 10^5
  • 1 \leq L_i \leq X_i \leq R_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 2
1 3 2
1 2 1

Sample Output 1

1

Only one permutation, P=(1,2,3), satisfies the conditions.

Sample Input 2

5 1
1 1 1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

1598400

Sample Input 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

Sample Output 4

921467228