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