平衡的多米诺骨牌放置

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个 $h$ 行 $w$ 列的棋盘，其中已经放置了若干块多米诺骨牌。每块骨牌覆盖两个相邻格子，且每个格子至多被覆盖一次。

若任意一行或一列中，被不同骨牌覆盖的格子不超过一个，则称放置是完全平衡的。换言之，一行或一列如果有两个格子被覆盖，这两个格子必须属于同一块骨牌。

现在给定一种完全平衡的初始放置。求有多少种方法可以在其基础上再放置零块或多块骨牌，并使最终放置仍然完全平衡。两种方案不同，当且仅当它们新放置的骨牌集合不同。

输入格式

第一行包含三个整数 $h,w,n$，分别表示棋盘的行数、列数和已有骨牌数。

接下来 $n$ 行，每行包含四个整数 $r_{i,1},c_{i,1},r_{i,2},c_{i,2}$，描述第 $i$ 块骨牌覆盖的两个相邻格子。

输出格式

输出合法扩展方案数对 $998244353$ 取模后的结果。

样例输入 1

5 7 2
3 1 3 2
4 4 4 5

样例输出 1

8

样例输入 2

5 4 2
1 2 2 2
4 3 4 4

样例输出 2

1

样例输入 3

23 42 0

样例输出 3

102848351

数据范围

$1\le h,w\le3600$，$0\le n\le2400$。输入保证所有骨牌均覆盖相邻格子，且初始放置完全平衡。

每个测试点独立计分。