E. Перманент
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Little X на днях решил #P полную задачу за полиномиальное время. Теперь он задает эту задачу вам!

Дана особая матрица A размера n × n, ваша задача — подсчитать ее перманент по модулю 1000000007 (109 + 7). Особое свойство матрицы A заключается в том, что почти все ее элементы равняются 1. Только k элементов имеют заданное значение.

Определение перманента можно найти по следующей ссылке: https://ru.wikipedia.org/wiki/Перманент

Входные данные

В первой строке записано два целых числа через пробел, n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 50).

В следующих k строках записано описание матрицы. В i-й строке записано три целых числа через пробел xi, yi, wi (1 ≤ xi,  yi ≤  n; 0  ≤  wi  ≤ 109). Эти числа обозначают, что Axi, yi = wi. Все элементы матрицы, кроме заданных, равны 1.

Гарантируется, что все позиции (xi, yi) различны.

Выходные данные

Выведите перманент матрицы по модулю 1000000007 (109  +  7).

Примеры
Входные данные
3 1
1 1 2
Выходные данные
8
Входные данные
10 10
3 3 367056794
6 2 124561273
1 3 46718146
6 9 415916869
10 5 985968336
3 1 526792265
1 4 386357058
10 4 349304187
2 7 102032499
3 6 502679075
Выходные данные
233333333