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
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач