問題文

整数 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

入力例 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