矩阵归零 - 問題

给定一个由 $ 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 $ 意义下的期望操作次数。

样例数据

样例 1 输入

样例 1 输出

样例 1 解释

打乱后的矩阵长这样:

子任务

子任务 $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 $。

QOJ.ac

QOJ