← 返回题目列表

AtCoder · utpc2022_k

K. 网格着色

中文机器翻译题面 查看原题

配点 : 100 点

問題文

2N\times 2M 。从上面 i 行,从左起 j 列网格 由 (i,j) 代表。最初,每个方块的颜色都是白色的。

从现在开始,将满足以下条件。 将 NM 方块涂成红色。

  • 涂成红色的方块 (i,j) 由递推公式 i+j 是偶数。
  • 涂成红色的方块不共享端点。从技术上讲,它被漆成红色。 2 3 个不同的方块 (i,j),(k,l) 和 没有什么可以满足|i-k|\leq 1 和 |j-l| \leq 1 。
  • K 方块 (X_i,Y_i) 必须涂成红色。

满足条件 将 NM 方格涂成红色的方法数为 998244353 取余。起初,数列

制約

  • 所有输入均为整数
  • 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 是偶数

入力

输入是按以下格式从标准输入给出的。

N M K
X_1 Y_1
X_2 Y_2
\vdots
X_K Y_K

出力

答案 1 行输出。 由于字符串以


入力例 1

2 2 1
3 1

出力例 1

3

例如,网格 将 (1,1),(2,4),(3,1),(4,4) 涂成红色就满足条件(见下左图)。

另一方面,网格 如果将 (1,1),(2,4),(3,1),(3,3) 涂成红色,它就会变成正方形。 (2,4),(3,3) 共享端点,因此不满足条件(见下右图)。 编号为


入力例 2

1 2 2
1 1
2 2

出力例 2

0

入力例 3

20 20 10
26 26
27 9
7 21
38 20
30 34
36 14
17 7
30 40
19 3
38 8

出力例 3

908257345