問題文

2N\times 2M のグリッド状のマス目があります。上から i 行目、左から j 列目のマス目を (i,j) で表します。はじめ、各マスの色はすべて白色です。

これから以下の条件を満たすように NM 個のマス目を赤く塗ります。

• 赤く塗られたマス目 (i,j) について i+j は偶数である。
• 赤く塗られたマス目は端点を共有しない。厳密には、赤く塗られた 2 つの異なるマス目 (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 は偶数

入力例 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