← 返回题目列表

AtCoder · pakencamp_2025_day3_a

A. 01 矩阵

中文机器翻译题面 查看原题

配点 : 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 时不要忘记求余数。