D. Количество перестановок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано $$$n$$$ пар чисел: $$$(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$$$. Последовательность считается плохой, если она отсортирована в порядке неубывания по первым элементам или если она отсортирована в порядке неубывания по вторым элементам. Иначе последовательность считается хорошей. Примеры хороших и плохих последовательностей:

  • $$$s = [(1, 2), (3, 2), (3, 1)]$$$ — плохая, потому что последовательность первых элементов отсортирована: $$$[1, 3, 3]$$$;
  • $$$s = [(1, 2), (3, 2), (1, 2)]$$$ — плохая, потому что последовательность вторых элементов отсортирована: $$$[2, 2, 2]$$$;
  • $$$s = [(1, 1), (2, 2), (3, 3)]$$$ — плохая, потому что обе последовательности (последовательность первых элементов и последовательность вторых элементов) отсортированы;
  • $$$s = [(1, 3), (3, 3), (2, 2)]$$$ — хорошая, потому что обе последовательности (последовательность первых $$$([1, 3, 2])$$$ и последовательность вторых элементов $$$([3, 3, 2])$$$) не отсортированы.

Посчитайте количество перестановок длины $$$n$$$ таких, что после применения этой перестановки к последовательности $$$s$$$ она станет хорошей последовательностью.

Перестановка $$$p$$$ длины $$$n$$$ это последовательность $$$p_1, p_2, \dots , p_n$$$ состоящая из $$$n$$$ различных чисел от $$$1$$$ до $$$n$$$ ($$$1 \le p_i \le n$$$). Если вы примените перестановку $$$p_1, p_2, \dots , p_n$$$ к последовательности $$$s_1, s_2, \dots , s_n$$$ вы получите последовательность $$$s_{p_1}, s_{p_2}, \dots , s_{p_n}$$$. Например, если $$$s = [(1, 2), (1, 3), (2, 3)]$$$ и $$$p = [2, 3, 1]$$$, то $$$s$$$ превратится $$$[(1, 3), (2, 3), (1, 2)]$$$.

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

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

Следующие $$$n$$$ строк содержат описание последовательности $$$s$$$. $$$i$$$-я строка содержит числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — первый и второй элементы $$$i$$$-й пары последовательности.

Последовательность $$$s$$$ может содержать одинаковые элементы.

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

Выведите количество перестановок длины $$$n$$$ таких, что после применения этой перестановки к последовательности $$$s$$$ она станет хорошей последовательностью. Так как количество таких перестановок может быть велико, выведите ответ по модулю $$$998244353$$$.

Примеры
Входные данные
3
1 1
2 2
3 1
Выходные данные
3
Входные данные
4
2 3
2 2
2 1
2 4
Выходные данные
0
Входные данные
3
1 1
1 1
2 3
Выходные данные
4
Примечание

В первом тестовом примере есть шесть перестановок длины $$$3$$$:

  1. если $$$p = [1, 2, 3]$$$, то $$$s = [(1, 1), (2, 2), (3, 1)]$$$ — плохая последовательность (отсортирована по первым элементам);
  2. если $$$p = [1, 3, 2]$$$, то $$$s = [(1, 1), (3, 1), (2, 2)]$$$ — плохая последовательность (отсортирована по вторым элементам);
  3. если $$$p = [2, 1, 3]$$$, то $$$s = [(2, 2), (1, 1), (3, 1)]$$$ — хорошая последовательность;
  4. если $$$p = [2, 3, 1]$$$, то $$$s = [(2, 2), (3, 1), (1, 1)]$$$ — хорошая последовательность;
  5. если $$$p = [3, 1, 2]$$$, то $$$s = [(3, 1), (1, 1), (2, 2)]$$$ — плохая последовательность (отсортирована по вторым элементам);
  6. если $$$p = [3, 2, 1]$$$, то $$$s = [(3, 1), (2, 2), (1, 1)]$$$ — хорошая последовательность.