AT_pakencamp_2025_day3_a 01 Matrix

$ N $ 行 $ M $ 列の $ 0,1 $ からなる行列 $ A=(A_{i,j}) $ $ (1\leq i\leq N,1\leq j\leq M) $ は $ 2^{NM} $ 通りありますが、そのうち以下の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - $ k=1,2,\dots,K $ のすべてについて、以下の両方が成り立つ。 - $ \displaystyle\sum_{i=1}^{x_{k}} \displaystyle\sum_{j=1}^{y_{k}} A_{i,j} $ が奇数 - $ \displaystyle\sum_{i=x_{k}+1}^{N} \displaystyle\sum_{j=y_{k}+1}^{M} A_{i,j} $ が奇数

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_K $ $ y_K $

答えを出力せよ。

### Sample Explanation 1 下図上の行列は条件を満たします。しかし、下の行列は条件を満たしません。 $ \displaystyle\sum_{i=1}^{x_1} \sum_{j=1}^{y_1} A_{i,j} $ が偶数であるためです。  ### Sample Explanation 2 答えを $ 998244353 $ で割った余りを求めることを忘れないでください。 ### Constraints - $ 2\leq N,M\leq 10^9 $ - $ 1\leq K\leq 3\times 10^5 $ - $ 1\leq x_i< N $ $ (1\leq i\leq K) $ - $ 1\leq y_i< M $ $ (1\leq i\leq K) $ - $ (x_i,y_i)\ne(x_j,y_j) $ $ (i\ne j) $ - 入力はすべて整数