F. Сбалансированные расположения домино
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим прямоугольную доску из $$$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$$$.

Примеры
Входные данные
5 7 2
3 1 3 2
4 4 4 5
Выходные данные
8
Входные данные
5 4 2
1 2 2 2
4 3 4 4
Выходные данные
1
Входные данные
23 42 0
Выходные данные
102848351
Примечание

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

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

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

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