Problem Description

Given integers \( N \) and \( M \) triplets of integers \( (A_i, B_i, C_i) \) (\( 1 \leq i \leq M \)). Find the number of permutations \( p \) of \( 1, 2, \ldots, N \) that satisfy the following condition for all \( i \) (\( 1 \leq i \leq M \)) modulo \( 10^9 + 7 \).

• When all permutations of length \( N \) are arranged in lexicographical order, there exists a permutation \( q = [q_1, q_2, \ldots, q_N] \) that follows \( p \) by \( A_i \) positions, and \( q_{B_i} = C_i \).

In the above condition, if \( A_i = 0 \), \( q \) is considered to be \( p \) itself.

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( A_1 \) \( B_1 \) \( C_1 \) \( A_2 \) \( B_2 \) \( C_2 \) \( : \) \( A_M \) \( B_M \) \( C_M \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 1
1 2 2

Sample Output #1

1

Sample Input #2

10 2
10 10 10
11 10 10

Sample Output #2

0

Sample Input #3

20 2
0 1 1
50 1 2

Sample Output #3

50

Sample Input #4

50 0

Sample Output #4

318608048

Sample Input #5

30 5
27 18 22
43 19 26
27 26 13
22 9 27
31 20 12

Sample Output #5

440732388

Notes/Hints

Constraints

• \( 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 \))
• For \( i \neq j \), \( A_i \neq A_j \) or \( B_i \neq B_j \) or \( C_i \neq C_j \)

Sample Explanation 1

When all permutations of \( 1, 2, 3 \) are arranged in lexicographical order, they are \( [1, 2, 3] \), \( [1, 3, 2] \), \( [2, 1, 3] \), \( [2, 3, 1] \), \( [3, 1, 2] \), \( [3, 2, 1] \). Among these, only the permutation \( [3, 1, 2] \) satisfies the condition.

见题面 Input 部分

见题面 Output 部分