配点 : 100 点
問題文
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} 是奇数
制約
- 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)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M K x_1 y_1 x_2 y_2 \vdots x_K y_K
出力
打印答案。 来自
入力例 1
3 4 2 2 2 1 3
出力例 1
256
下图中的矩阵满足条件。然而,下面的矩阵不满足条件。 这是因为\displaystyle\sum_{i=1}^{x_1} \sum_{j=1}^{y_1} A_{i,j} 是偶数。

入力例 2
76 38 4 7 6 3 8 20 26 3 28
出力例 2
361562686
答案 请打印除以 998244353 时不要忘记求余数。