题目描述

给定一个由 $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$ ，请输出 $PQ^{-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$（$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$。