配点 : 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