CF1237F.Balanced Domino Placements

Consider a square grid with $h$ rows and $w$ columns with some dominoes on it. Each domino covers exactly two cells of the grid that share a common side. Every cell is covered by at most one domino.

Let's call a placement of dominoes on the grid perfectly balanced if no row and no column contains a pair of cells covered by two different dominoes. In other words, every row and column may contain no covered cells, one covered cell, or two covered cells that belong to the same domino.

You are given a perfectly balanced placement of dominoes on a grid. Find the number of ways to place zero or more extra dominoes on this grid to keep the placement perfectly balanced. Output this number modulo $998\,244\,353$.

考虑一个 $h$ 行 $w$ 列的方格网格，其上已放置若干张多米诺骨牌。每张多米诺骨牌恰好覆盖网格中两个具有公共边的格子。每个格子至多被一张多米诺骨牌覆盖。

若网格上的多米诺骨牌排布满足：任意一行与任意一列均不包含被两张不同多米诺骨牌所覆盖的两个格子，则称该排布为完美平衡的。换言之，每一行和每一列中，被覆盖的格子数量可以是 $0$ 个、$1$ 个，或 $2$ 个——但若为 $2$ 个，则它们必须属于同一张多米诺骨牌。

现给定一个完美平衡的多米诺骨牌排布。求在该网格上额外放置零张或多张多米诺骨牌，使得最终排布仍保持完美平衡的方案总数。输出该数对 $998\,244\,353$ 取模的结果。

The first line contains three integers $h$, $w$, and $n$ ($1 \le h, w \le 3600$; $0 \le n \le 2400$), denoting the dimensions of the grid and the number of already placed dominoes. The rows are numbered from $1$ to $h$, and the columns are numbered from $1$ to $w$.

Each of the next $n$ lines contains four integers $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$), denoting the row id and the column id of the cells covered by the $i$-th domino. Cells $(r_{i, 1}, c_{i, 1})$ and $(r_{i, 2}, c_{i, 2})$ are distinct and share a common side.

The given domino placement is perfectly balanced.

第一行包含三个整数 $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})$ 互不相同，且具有公共边。

给定的多米诺骨牌摆放是完全平衡的。

Output the number of ways to place zero or more extra dominoes on the grid to keep the placement perfectly balanced, modulo $998\,244\,353$.

输出在网格上放置零个或多个额外多米诺骨牌以保持布局完全平衡的方法数，对 $998\,244\,353$ 取模。

In the first example, the initial grid looks like this:

Here are $8$ ways to place zero or more extra dominoes to keep the placement perfectly balanced:

In the second example, the initial grid looks like this:

No extra dominoes can be placed here.

在第一个例子中，初始网格如下所示：

以下是 $8$ 种放置零个或多个额外多米诺骨牌的方式，使得整体摆放保持完美平衡：

在第二个例子中，初始网格如下所示：

此处无法放置任何额外的多米诺骨牌。