6781. 矩阵归零

题目描述

给定一个由 $0$ 和 $1$ 组成的 $n \times m$ 矩阵，定义一次操作 $(x, y)$ 是将第 $x$ 行和第 $y$ 列上的所有元素取反，即 $0$ 变 $1$，$1$ 变 $0$，$(x, y)$ 会被取反两次。一开始矩阵上每个元素都为零，先对矩阵操作 $k$ 次 $(x_1, y_1) \sim (x_k, y_k)$ 进行打乱，打乱后每次等概率的选择一个位置操作直到矩阵归零，求使矩阵归零的期望操作次数。

若期望次数为 $\frac{P}{Q}$，其中 $P \ge 0$, $Q > 0$ 且 $\operatorname{gcd}(P, Q) = 1$，请输出 $P \times Q^{-1} \bmod 998244353$。

输入格式

第一行三个正整数 $n$, $m$, $k$。

之后的 $k$ 行，每行两个正整数 $x_i$, $y_i$ 表示第 $i$ 次操作。

输出格式

输出模 $998244353$ 意义下的期望操作次数。

样例

输入

4 3 5
3 2
2 3
3 1
4 3
4 2

输出

63

打乱后的矩阵长这样：

1 0 0
0 1 1
1 0 0
1 0 0

数据范围与提示

子任务分布：

• 子任务 1（15%）：$1 \leq n \times m \leq 1000$
• 子任务 2（15%）：$1 \leq n \times m \leq 5000$
• 子任务 3（20%）：$1 \leq n, m \leq 500$
• 子任务 4（20%）：$1 \leq n, m \leq 2000$
• 子任务 5（30%）：$1 \leq n, m \leq 50000$

对于 $100\%$ 的数据：

• $1 \leq k \leq 50000$
• $1 \leq x_i \leq n$
• $1 \leq y_i \leq m$