Two Options#13011

Two Options

4 seconds
512 megabytes
Very hard

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.

Input

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.

Output

Print a single number – the number of good permutations modulo 10^9+7.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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).