Given an $n \times m$ matrix consisting of $0$s and $1$s, an operation $(x, y)$ is defined as flipping all elements in row $x$ and column $y$ (i.e., $0$ becomes $1$, and $1$ becomes $0$). Note that the element at $(x, y)$ is flipped twice. Initially, all elements in the matrix are $0$. The matrix is first scrambled by performing $k$ operations $(x_1, y_1) \sim (x_k, y_k)$. After scrambling, in each step, a position $(x, y)$ is chosen uniformly at random to perform the operation until the matrix returns to all zeros. Find the expected number of operations required to make the matrix all zeros.

If the expected number of operations is $\frac{P}{Q}$, where $P \ge 0$, $Q > 0$, and $\operatorname{gcd}(P, Q) = 1$, output $PQ^{-1} \bmod 998244353$.

Input

The first line contains three positive integers $n, m, k$.

The following $k$ lines each contain two positive integers $x_i, y_i$, representing the $i$-th operation.

Output

Output the expected number of operations modulo $998244353$.

Examples

Input 1

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

Output 1

63

Note 1

The scrambled matrix looks like this:

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

Subtasks

• Subtask 1 ($15\%$): $1 \leq n \times m \leq 1000$;
• Subtask 2 ($15\%$): $1 \leq n \times m \leq 5000$;
• Subtask 3 ($20\%$): $1 \leq n, m \leq 500$;
• Subtask 4 ($20\%$): $1 \leq n, m \leq 2000$;
• Subtask 5 ($30\%$): $1 \leq n, m \leq 50000$;

For $100\%$ of the data, $1 \leq k \leq 50000$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$.