← 返回题目列表

Codeforces · 1207/D

D. 排列数

中文机器翻译题面 查看原题

给定一个 $$$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$$$ 后,它会变成一个好的序列。

大小为 $$$n$$$ 的排列 $$$p$$$ 是一个序列 $$$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$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

接下来的 $$$n$$$ 行包含序列 $$$s$$$ 的描述。第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — 序列中第 $$$i$$$ 对的第一个和第二个元素。

序列 $$$s$$$ 可以包含相等的元素。

输出

打印大小为 $$$n$$$ 的排列数,以便将此排列应用于序列 $$$s$$$ 后,它会变成一个好的序列。打印答案对 $$$998244353$$$(质数)取模。

示例

输入 #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

注意

在第一个测试用例中,有 6 个大小为 $$$3$$$ 的排列:

1. 如果 $$$p = [1, 2, 3]$$$,则 $$$s = [(1, 1), (2, 2), (3, 1)]$$$ — 错误序列(按第一个元素排序);
2. 如果 $$$p = [1, 3, 2]$$$,则 $$$s = [(1, 1), (3, 1), (2, 2)]$$$ — 错误序列(按第二个元素排序);
3. 如果 $$$p = [2, 1, 3]$$$,则 $$$s = [(2, 2), (1, 1), (3, 1)]$$$ — 良好的序列;
4. 如果 $$$p = [2, 3, 1]$$$,则 $$$s = [(2, 2), (3, 1), (1, 1)]$$$ — 良好的序列;
5. 如果 $$$p = [3, 1, 2]$$$,则 $$$s = [(3, 1), (1, 1), (2, 2)]$$$ — 错误序列(按第二个元素排序);
6. 如果 $$$p = [3, 2, 1]$$$,则 $$$s = [(3, 1), (2, 2), (1, 1)]$$$ — 良好的序列。