题目描述

在 $(1,2,\dots,N)$ 的所有排列 $P=(P_1,P_2,\dots,P_N)$ 中，满足以下所有条件的排列个数，输出其对 $998244353$ 取模的结果。

• 对于每个 $1\le i\le M$，都有 $\max(P_{A_i},P_{B_i})=C_i$。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

样例 1

输入

4 2
1 2 4
2 3 2

输出

2

样例 2

输入

6 3
1 4 3
2 5 6
3 4 2

输出

8

样例 3

输入

20 17
9 16 13
5 14 20
15 20 14
5 13 17
18 20 14
14 20 20
6 13 11
12 16 19
2 15 10
6 17 11
7 18 7
8 18 12
8 16 13
6 16 13
2 18 10
9 10 15
7 14 20

输出

1209600

说明/提示

限制条件

• $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$
• 若 $i\neq j$，则 $(A_i,B_i)\neq (A_j,B_j)$

样例解释 1

满足条件的 $P$ 有 $(4,1,2,3)$ 和 $(4,2,1,3)$，共 $2$ 个。

由 ChatGPT 4.1 翻译