最大值排列

时间限制：2s
空间限制：512MB

题目描述

求排列 $P=(P_1,P_2,\ldots,P_N)$ 的数量，使得它是 $1,2,\ldots,N$ 的一个排列，并满足下面的 $M$ 条限制：

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $N,M$。接下来 $M$ 行，每行三个整数 $A_i,B_i,C_i$。

输出格式

输出满足全部限制的排列数量对 $998244353$ 取模的结果。

样例输入 1

4 2
1 2 4
2 3 2

样例输出 1

2

样例输入 2

6 3
1 4 3
2 5 6
3 4 2

样例输出 2

8

样例解释

样例一中满足条件的排列为 $(4,1,2,3)$ 与 $(4,2,1,3)$。

数据范围

• $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)$ 互不相同。