← 返回题目列表

AtCoder · bitflyer2018_final_g

G. 以下排列

中文机器翻译题面 查看原题

配点 : 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 的排列按字典序排列时 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