D. Number Of Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

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

Examples
Input
3
1 1
2 2
3 1

Output
3

Input
4
2 3
2 2
2 1
2 4

Output
0

Input
3
1 1
1 1
2 3

Output
4

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.