Number Of Permutations

题意翻译

给定长度为 $n$ 的数对列 $s_1 \sim s_n$，其中 $s_i = (a_i, b_i)$ 给定。**好序列**的定义是：仅看第一关键字或第二关键字都不按升序排序的序列。 输出符合题意的大小为 $n$ 的排列的方案数，使得经过这些排列中的任何一个的排列操作之后，序列 $s$ 会成为一个**好序列**。答案对 $998244353$ 取模（一个质数）。

题目描述

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

输入输出样例

输入样例 #1

3
1 1
2 2
3 1

输出样例 #1

3

输入样例 #2

4
2 3
2 2
2 1
2 4

输出样例 #2

0

输入样例 #3

3
1 1
1 1
2 3

输出样例 #3

4

说明

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.