G - Following Permutations

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1100

問題文

整数 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 の置換をすべて辞書順に並べたとき pA_i 個あとにあたる置換 q = [q_1, q_2, ..., q_N] が存在し、q_{B_i} = C_i である。

なお、上の条件において、A_i = 0 のとき qp 自身であるとします。

制約

  • 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