CF1207D.Number Of Permutations

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)]$ .

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.

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).

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.