Дана матрица $n \times m$ из $0$ и $1$. Операция $(x, y)$ определяется как инвертирование всех элементов в $x$-й строке и $y$-м столбце (то есть $0$ меняется на $1$, а $1$ на $0$). Элемент на пересечении $(x, y)$ инвертируется дважды. Изначально все элементы матрицы равны $0$. Сначала матрица подвергается $k$ операциям $(x_1, y_1), \dots, (x_k, y_k)$ в заданном порядке. После этого мы каждый раз равновероятно выбираем позицию $(x, y)$ для выполнения операции до тех пор, пока матрица не станет нулевой. Найдите математическое ожидание количества операций, необходимых для обнуления матрицы.

Если ожидаемое количество операций равно $\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

Входные данные

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

Выходные данные

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$;

Для $100\%$ данных: $1 \leq k \leq 50000$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$.