AT_utpc2022_k Grid Coloring

$ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_K $ $ Y_K $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 例えばマス目 $ (1,1),(2,4),(3,1),(4,4) $ を赤く塗ると条件を満たします（下図左）。 一方、マス目 $ (1,1),(2,4),(3,1),(3,3) $ を赤く塗るとマス目 $ (2,4),(3,3) $ が端点を共有してしまっているため、条件を満たしません（下図右）。  ### Constraints - 入力は全て整数 - $ 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 $ は偶数