Вам задано \(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\) таких, что после применения этой перестановки к последовательности \(s\) она станет хорошей последовательностью. Так как количество таких перестановок может быть велико, выведите ответ по модулю \(998244353\).