Dany jest macierz $n \times m$ składająca się z $0$ i $1$. Operacja $(x, y)$ polega na odwróceniu wszystkich elementów w $x$-tym wierszu oraz $y$-tej kolumnie, co oznacza, że $0$ zmienia się w $1$, a $1$ w $0$. Element $(x, y)$ jest odwracany dwukrotnie. Początkowo wszystkie elementy macierzy są równe zero. Macierz zostaje poddana $k$ operacjom $(x_1, y_1) \sim (x_k, y_k)$ w celu jej przemieszania. Po przemieszaniu, w każdym kroku losowo wybieramy jedną pozycję $(x, y)$ i wykonujemy na niej operację, aż cała macierz wróci do stanu zerowego. Oblicz oczekiwaną liczbę operacji potrzebną do wyzerowania macierzy.

Jeśli oczekiwana liczba wynosi $\frac{P}{Q}$, gdzie $P \ge 0, Q > 0$ oraz $\operatorname{gcd}(P, Q) = 1$, wyprowadź $PQ^{-1} \bmod 998244353$.

Wejście

Pierwsza linia zawiera trzy liczby całkowite dodatnie $n, m, k$.

Następnie $k$ linii, z których każda zawiera dwie liczby całkowite dodatnie $x_i, y_i$, oznaczające $i$-tą operację.

Wyjście

Wyprowadź oczekiwaną liczbę operacji modulo $998244353$.

Przykład

Przykład 1

Wejście:

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

Wyjście:

63

Uwagi

Po przemieszaniu macierz wygląda następująco:

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

Podzadania

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

Dla $100\%$ danych wejściowych: $1 \leq k \leq 50000$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$.