Problem Statement

Print the number, modulo $998244353$, of permutations $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ that satisfy all of the following conditions:

• $\max(P_{A_i},P_{B_i}) = C_i\ (1 \le i \le M)$.

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i < B_i \le N$
• $1 \le C_i \le N$
• $(A_i,B_i) \neq (A_j,B_j)$ if $i \neq j$.

Input

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

Print the answer.