Два варіанти

Обмеження: 4 сек., 512 МіБ

Вам задано два цілі числа \(n\) та \(m\), а також \(m\) трійок цілих чисел \((i, j, x)\), де \(1 \le i < j \le n\), \(1 \le x \le n\).

Перестановка \(p = (p_1, p_2, \dots, p_n)\) чисел \(1, 2, \dots, n\) називається хорошою, якщо для кожної із заданих трійок \((i, j, x)\) виконується хоча б одна з умов: \(p_i = x\) або \(p_j = x\).

Обчисліть кількість хороших перестановок і виведіть відповідь за модулем \(10^9+7\).

Вхідні дані

У першому рядку задано два цілі числа \(n\) та \(m\) — розмір перестановки \(p\) та кількість трійок.

У наступних \(m\) рядках задано по три цілі числа \(i\), \(j\) та \(x\), що описують трійки.

Вихідні дані

Виведіть одне ціле число — кількість хороших перестановок за модулем \(10^9+7\).

Обмеження

\(2 \le n \le 10^6\),

\(1 \le m \le 10^6\),

\(1 \le i < j \le n\),

\(1 \le x \le n\),

усі трійки попарно різні.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 1 2 1 1 3 1 2 3 2 2 3 3	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 7 1 2 1 1 3 1 1 4 1 1 2 2 2 3 2 2 4 2 3 4 4	2

Примітки

У першому прикладі \(n=4\), \(m=4\). Хороші перестановки повинні задовольняти всі наведені нижче умови.

• \(p_1 = 1\) або \(p_2 = 1\).

• \(p_1 = 1\) або \(p_3 = 1\).

• \(p_2 = 2\) або \(p_3 = 2\).

• \(p_2 = 3\) або \(p_3 = 3\).

Існують дві хороші перестановки: \((1, 2, 3)\) та \((1, 3, 2)\).

У другому прикладі хорошими є перестановки \((1, 2, 3, 4)\) та \((1, 2, 4, 3)\).