Недавно оказалось, что все экономическое состояние Берляндии на данный момент можно описать при помощи простой таблицы размера n × m. n — количество дней в каждом берляндском месяце, m — количество месяцев. Таким образом, клетка таблицы соответствует дню и месяцу берляндского года. В каждой клетке будет записано либо 1, либо -1, что означает доход государства в какой-то конкретный месяц и день, где 1 соответствует прибыли, -1 соответствует убытку. Для успешного развития оказалось важным проанализировать данные об экономическом состоянии прошлого года, но когда казначеи обратились в архив за данными, оказалось, что таблица была очень существенно испорчена. В некоторых клетках таблицы значения чисел стерлись, и теперь разобрать их невозможно. Известно, что количество клеток, где данные сохранились, строго меньше max(n, m). Однако, есть дополнительная информация — произведение чисел в каждой строке и в каждом столбце было равно -1. От вас требуется найти, сколько различных таблиц может соответствовать данным, которые сохранились. Так как ответ на задачу может быть достаточно большим, требуется найти его по модулю p.
В первой строке записаны числа n и m (1 ≤ n, m ≤ 1000). Во второй строке записано число k (0 ≤ k < max(n, m)) — количество клеток, где данные сохранились. В следующих k строках записаны данные о состоянии таблицы в сохраненных клетках. Каждая строка имеет вид "a b c", где a (1 ≤ a ≤ n) — номер строки в таблице, b (1 ≤ b ≤ m) — номер столбца, c — значение в клетке (1 или -1). Нумерация ведется с 1. Гарантируется, что нет двух строк с одинаковыми значениями a и b. В последней строке записано число p (2 ≤ p ≤ 109 + 7).
Вывести количество различных таблиц, которые могут соответствовать сохраненным данным, по модулю p.
2 2
0
100
2
2 2
1
1 1 -1
100
1
| Codeforces Beta Round 39 |
|---|
| Закончено |
