Problem Description

Given a permutation \( P = (P_1, P_2, \cdots, P_N) \) of \( (1, 2, \cdots, N) \), find the number of such permutations that satisfy all \( M \) conditions, modulo \( 998244353 \).

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

Input Format

The input is provided 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 Format

Output the answer.

Sample Input and Output

Sample Input #1

3 2
1 3 2
1 2 1

Sample Output #1

1

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

Notes/Hints

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.

Sample Explanation 1

The only permutation that satisfies the conditions is \( P = (1, 2, 3) \).

见题面 Input 部分

见题面 Output 部分