You are given two integers and , and triplets of integers (i, j, x), where 1 \le i < j \le n, 1 \le x \le n.
Permutation p = (p_1, p_2, \dots, p_n) of integers 1, 2, \dots, n is good if for all given triplets (i, j, x), it holds that either p_i = x or p_j = x.
Calculate the number of good permutations, and print the answer modulo 10^9+7.
The first line contains two integers and – the size of the permutation and the number of triplets.
The next lines contain three integers , , and , describing the triplets.
2 \le n \le 10^6,
1 \le m \le 10^6,
1 \le i < j \le n,
1 \le x \le n,
all the triplets are pairwise distinct.
Print a single number – the number of good permutations modulo 10^9+7.
Example
Example 1
In the first sample, n=4, m=4. Good permutations must satisfy all of the following conditions.
p_1 = 1 or p_2 = 1.
p_1 = 1 or p_3 = 1.
p_2 = 2 or p_3 = 2.
p_2 = 3 or p_3 = 3.
There are two good permutations: (1, 2, 3) and (1, 3, 2).
In the second sample, the good permutations are (1, 2, 3, 4) and (1, 2, 4, 3).