Balanced Domino Placements

Description:

Input:

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.

Output:

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$$$.

Sample Input:

5 7 2
3 1 3 2
4 4 4 5

Sample Output:

8

Sample Input:

5 4 2
1 2 2 2
4 3 4 4

Sample Output:

1

Sample Input:

23 42 0

Sample Output:

102848351

Note:

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.