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.