Two Options

Limits: 4 sec., 512 MiB

You are given two integers \(n\) and \(m\), and \(m\) 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 \(m\) 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 \(n\) and \(m\) – the size of the permutation \(p\) and the number of triplets.

The next \(m\) lines contain three integers \(i\), \(j\), and \(x\), describing the triplets.

Output

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

Constraints

\(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.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 4 1 2 1 1 3 1 2 3 2 2 3 3	2

Input (stdin) сopy	Output (stdout) сopy
4 7 1 2 1 1 3 1 1 4 1 1 2 2 2 3 2 2 4 2 3 4 4	2

Notes

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