問題文

整数 $N$ および $M$ 個の整数の $3$ つ組 $(A_i, B_i, C_i)$ ($1 \\leq i \\leq M$) が与えられます。 $1, 2, ..., N$ の置換 $p$ であって、すべての $i$ ($1 \\leq i \\leq M$) に対して以下の条件を満たすものの個数を $10^9 + 7$ で割ったあまりを求めてください。

• 長さ $N$ の置換をすべて辞書順に並べたとき $p$ の $A_i$ 個あとにあたる置換 q = \[q_1, q_2, ..., q_N\] が存在し、$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