AT_utpc2022_k.Grid Coloring

有一个 $2N \times 2M$ 的网格，网格的每个格子用 $(i,j)$ 表示，其中 $i$ 表示从上往下的第 $i$ 行，$j$ 表示从左往右的第 $j$ 列。起初，每个格子的颜色都是白色。

现在要将 $NM$ 个格子染成红色，并使其满足以下条件：

• 对于被染成红色的格子 $(i,j)$，$i + j$ 必须是偶数。
• 被染成红色的格子之间不能共享角或边。严格来说，任意两个不同的被染成红色的格子 $(i,j)$、$(k,l)$，不允许满足 $|i-k| \leq 1$ 且 $|j-l| \leq 1$。
• $K$ 个指定的格子 $(X_i, Y_i)$ 必须染成红色。

请计算，使 $NM$ 个格子染成红色且满足上述所有条件的方法数，对 $998244353$ 取模。

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\cdots$ $X_K$ $Y_K$

输出一个整数，表示满足条件的方案数。

样例解释 1

例如，将格子 $(1,1),(2,4),(3,1),(4,4)$ 染成红色，就满足条件（见下图左）。

而如果将格子 $(1,1),(2,4),(3,1),(3,3)$ 染成红色，则由于格子 $(2,4)$ 与 $(3,3)$ 共享角，故不满足条件（见下图右）。

数据范围

• 输入均为整数
• $1 \leq N, M \leq 3000$
• $0 \leq K \leq \min(NM, 10^5)$
• $1 \leq X_i \leq 2N, 1 \leq Y_i \leq 2M$
• $(X_i,Y_i)$ 互不相同
• $X_i + Y_i$ 是偶数

由 ChatGPT 5 翻译