问题文

给定整数N和M个整数的三元组$(A_i, B_i, C_i)$ $(1 \leq i \leq M)$。请计算满足以下条件的长度为N的排列p的数量（对$10^9 + 7$ 取模）：

• 当对于所有的i $(1 \leq i \leq M)$，在将长度为N的排列按字典顺序排列后，存在一个排列q = $[q_1, q_2, ..., q_N]$使得q在p后面第$A_i$个，并且$q_{B_i} = C_i$。

在上述条件中，当$A_i = 0$时，q被认为是p本身。

约束条件

• $1 \leq N \leq 50$
• $0 \leq M \leq 50$
• $0 \leq A_i \leq 50$ $(1 \leq i \leq M)$
• $A_i \leq N! - 1$ $(1 \leq i \leq M)$
• $1 \leq B_i, C_i \leq N$ $(1 \leq i \leq M)$
• 对于$i \neq j$，$A_i \neq A_j$ 或 $B_i \neq B_j$ 或 $C_i \neq C_j$

---

输入

输入以以下格式从标准输入中给出。

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

输出

输出答案。

---

示例输入 1

3 1
1 2 2

示例输出 1

1

将$1, 2, 3$的排列按字典顺序排列得到 \[1, 2, 3\], \[1, 3, 2\], \[2, 1, 3\], \[2, 3, 1\], \[3, 1, 2\], \[3, 2, 1\]。满足条件的排列只有 \[3, 1, 2\]。

---

示例输入 2

10 2
10 10 10
11 10 10

示例输出 2

0

---

示例输入 3

20 2
0 1 1
50 1 2

示例输出 3

50

---

示例输入 4

50 0

示例输出 4

318608048

---

示例输入 5

30 5
27 18 22
43 19 26
27 26 13
22 9 27
31 20 12

示例输出 5

440732388