AT_bitflyer2018_final_g Following Permutations

给定一个整数 $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$ 的排列按字典序排列后，排列 $p$ 排在第 $A_i$ 个之后的排列 $q = [q_1, q_2, \ldots, q_N]$ 必须满足 $q_{B_i} = C_i$。 特别地，如果 $A_i = 0$，那么 $q$ 即是排列 $p$ 本身。

输入由以下格式构成： > $N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ ... $A_M$ $B_M$ $C_M$

输出符合条件的排列数量对 $10^9 + 7$ 取模后的结果。

- $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$ ### 样例解释 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]$ 满足条件。 **本翻译由 AI 自动生成**