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 翻译