AT_bitflyer2018_final_g Following Permutations

[problemUrl]: https://atcoder.jp/contests/bitflyer2018-final/tasks/bitflyer2018_final_g 整数 $ 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 $ 自身であるとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ : $ $ A_M $ $ B_M $ $ C_M $

答えを出力せよ。

### 制約 - $ 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 $ ### Sample Explanation 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] $ だけです。