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

Задача . F. Сбалансированные расположения домино

Задача

Рассмотрим прямоугольную доску из $h$ строк и $w$ столбцов, на которой расположены костяшки домино. Каждая костяшка покрывает ровно две клетки доски, которые имеют общую сторону. Каждая клетка покрыта не более чем одной костяшкой.

Будем называть расположение домино на доске идеально сбалансированным, если никакая строка и никакой столбец не содержит пару клеток, покрытых разными костяшками. Другими словами, каждая строка и каждый столбец может не содержать ни одной покрытой клетки, содержать одну покрытую клетку либо содержать две покрытые клетки, принадлежащие одной костяшке.

Вам дано идеально сбалансированное расположение домино на доске. Найдите число способов разместить ноль или более дополнительных костяшек на этой доске, чтобы расположение осталось идеально сбалансированным. Выведите это число по модулю $998\,244\,353$.

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

Первая строка содержит три целых числа $h$, $w$ и $n$ ($1 \le h, w \le 3600$; $0 \le n \le 2400$) — размерности доски и число уже размещённых костяшек. Строки пронумерованы от $1$ до $h$, а столбцы пронумерованы от $1$ до $w$.

Каждая из следующих $n$ строк содержит четыре целых числа $r_{i, 1}, c_{i, 1}, r_{i, 2}, c_{i, 2}$ ($1 \le r_{i, 1} \le r_{i, 2} \le h$; $1 \le c_{i, 1} \le c_{i, 2} \le w$) — номера строк и столбцов клеток, покрытых $i$-й костяшкой. Клетки $(r_{i, 1}, c_{i, 1})$ и $(r_{i, 2}, c_{i, 2})$ различны и имеют общую сторону.

Заданное расположение домино идеально сбалансировано.

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

Выведите число способов разместить ноль или более дополнительных костяшек на доске, чтобы расположение осталось идеально сбалансированным, по модулю $998\,244\,353$.

Примечание

В первом примере заданная доска выглядит так:

$\text{[math]}$

Вот $8$ способов разместить ноль или более дополнительных костяшек, чтобы расположение осталось идеально сбалансированным:

$\text{[math]}$

Во втором примере заданная доска выглядит так:

$\text{[math]}$

Ни одной дополнительной костяшки разместить нельзя.

Примеры

№	Входные данные	Выходные данные
1	5 7 2 3 1 3 2 4 4 4 5	8
2	5 4 2 1 2 2 2 4 3 4 4	1
3	23 42 0	102848351

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

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	5

Комментарий учителя

Ваш ответ

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

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

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

Нет