配点 : 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