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$ 的所有 $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$

请输出答案。

### 样例解释 1 下图上的矩阵满足条件。下图下方的矩阵不满足条件，因为 $\displaystyle\sum_{i=1}^{x_1} \sum_{j=1}^{y_1} A_{i,j}$ 是偶数。  ### 样例解释 2 不要忘记对答案取 $998244353$ 的余数。 ### 数据范围 - $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)\neq(x_j,y_j)$ $(i\neq j)$ - 所有输入均为整数。 由 ChatGPT 5 翻译