Number Of Permutations
Contest: Educational Codeforces Round 71 (Rated for Div. 2)
Difficulty rating: 1800
Tags: combinatorics

You are given a sequence of $$$n$$$ pairs of integers: $$$(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$$$. This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:

- $$$s = [(1, 2), (3, 2), (3, 1)]$$$ is bad because the sequence of first elements is sorted: $$$[1, 3, 3]$$$;
- $$$s = [(1, 2), (3, 2), (1, 2)]$$$ is bad because the sequence of second elements is sorted: $$$[2, 2, 2]$$$;
- $$$s = [(1, 1), (2, 2), (3, 3)]$$$ is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;
- $$$s = [(1, 3), (3, 3), (2, 2)]$$$ is good because neither the sequence of first elements $$$([1, 3, 2])$$$ nor the sequence of second elements $$$([3, 3, 2])$$$ is sorted.

Calculate the number of permutations of size $$$n$$$ such that after applying this permutation to the sequence $$$s$$$ it turns into a good sequence.

A permutation $$$p$$$ of size $$$n$$$ is a sequence $$$p_1, p_2, \dots , p_n$$$ consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ ($$$1 \le p_i \le n$$$). If you apply permutation $$$p_1, p_2, \dots , p_n$$$ to the sequence $$$s_1, s_2, \dots , s_n$$$ you get the sequence $$$s_{p_1}, s_{p_2}, \dots , s_{p_n}$$$. For example, if $$$s = [(1, 2), (1, 3), (2, 3)]$$$ and $$$p = [2, 3, 1]$$$ then $$$s$$$ turns into $$$[(1, 3), (2, 3), (1, 2)]$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The next $$$n$$$ lines contains description of sequence $$$s$$$. The $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — the first and second elements of $$$i$$$-th pair in the sequence.

The sequence $$$s$$$ may contain equal elements.

Output format:
Print the number of permutations of size $$$n$$$ such that after applying this permutation to the sequence $$$s$$$ it turns into a good sequence. Print the answer modulo $$$998244353$$$ (a prime number).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In first test case there are six permutations of size $$$3$$$:

1. if $$$p = [1, 2, 3]$$$, then $$$s = [(1, 1), (2, 2), (3, 1)]$$$ — bad sequence (sorted by first elements);
2. if $$$p = [1, 3, 2]$$$, then $$$s = [(1, 1), (3, 1), (2, 2)]$$$ — bad sequence (sorted by second elements);
3. if $$$p = [2, 1, 3]$$$, then $$$s = [(2, 2), (1, 1), (3, 1)]$$$ — good sequence;
4. if $$$p = [2, 3, 1]$$$, then $$$s = [(2, 2), (3, 1), (1, 1)]$$$ — good sequence;
5. if $$$p = [3, 1, 2]$$$, then $$$s = [(3, 1), (1, 1), (2, 2)]$$$ — bad sequence (sorted by second elements);
6. if $$$p = [3, 2, 1]$$$, then $$$s = [(3, 1), (2, 2), (1, 1)]$$$ — good sequence.

Example input:
3
1 1
2 2
3 1

Example output:
3

Example input:
4
2 3
2 2
2 1
2 4

Example output:
0

Editorial:
Let's suppose that all $$$n!$$$ permutation are good. We counted the permutations giving the sequences where the first elements are sorted (we denote the number of such permutations as $$$cnt_1$$$) and the permutations giving the sequences where the second elements are sorted (we denote the number of such permutations as $$$cnt_2$$$). Then the answer is $$$n! - cnt_1 - cnt_2$$$, right? No, because we subtracted the number of sequences where first and second elements are sorted simultaneously (we denote this number as $$$cnt_{12}$$$) twice. So, the answer is $$$n! - cnt_1 - cnt_2 + cnt_{12}$$$.
How can we calculate the value of $$$cnt_1$$$? It's easy to understand that the elements having equal $$$a_i$$$ can be arranged in any order. So, $$$cnt_1 = c_1! ~ c_2! ~ \dots ~ c_n!$$$, where $$$c_x$$$ is the number of elements equal to $$$x$$$ among $$$a_i$$$. $$$cnt_2$$$ can be calculated the same way.
How can we calculate the value of $$$cnt_{12}$$$? First of all, there is a case where it is impossible to arrange the elements of the sequence so that the first elements and the second elements are sorted. To check that, we may sort the given sequence comparing two elements by $$$a_i$$$, and if $$$a_i$$$ are equal — by $$$b_i$$$. If the sequence of second elements in the resulting sequence is not sorted, then $$$cnt_{12} = 0$$$. Otherwise, equal elements of the given sequence can be arranged in any order. So $$$cnt_{12} = c_{s_1}! ~ c_{s_2}! ~ c_{s_k}!$$$, where $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$ are the elements that appear in the given sequence of pairs at least once.