$0$ と $1$ からなる $n \times m$ 行列が与えられる。操作 $(x, y)$ を、第 $x$ 行と第 $y$ 列のすべての要素を反転させる（$0$ は $1$ に、$1$ は $0$ になる）ことと定義する。なお、$(x, y)$ の交点にある要素は二度反転される。最初、行列のすべての要素は $0$ である。まず、行列に対して $k$ 回の操作 $(x_1, y_1) \sim (x_k, y_k)$ を行い、行列を乱す。その後、行列がすべて $0$ になるまで、毎回等確率で位置 $(x, y)$ を選択して操作を行う。行列がすべて $0$ になるまでの操作回数の期待値を求めよ。

期待値が $\frac{P}{Q}$ （ただし $P \ge 0, Q > 0, \operatorname{gcd}(P, Q) = 1$）であるとき、$PQ^{-1} \bmod 998244353$ を出力せよ。

入力

1行目に3つの正整数 $n, m, k$ が与えられる。

続く $k$ 行には、各操作を表す2つの正整数 $x_i, y_i$ が与えられる。

出力

$998244353$ を法とする期待操作回数を出力せよ。

入出力例

入力 1

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

出力 1

63

注記 1

乱した後の行列は以下のようになる：

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$

すべてのデータにおいて、$1 \leq k \leq 50000$、$1 \leq x_i \leq n$、$1 \leq y_i \leq m$ を満たす。