Олимпиадный тренинг

Задача . E. Перманент


Задача

Темы: meet-in-the-middle дп математика Паросочетания *3100

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


Примеры
№Входные данныеВыходные данные
1 3 1
1 1 2 
8
2 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

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет