Два варіанти#13011

Два варіанти

Вам задано два цілі числа та , а також трійок цілих чисел (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.

Вхідні дані

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

У наступних рядках задано по три цілі числа , та , що описують трійки.

2 \le n \le 10^6,

1 \le m \le 10^6,

1 \le i < j \le n,

1 \le x \le n,

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

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі 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).