题目描述

题目来自 USACO 2024 January Contest, Platinum Problem 3. Mooball Teams III

Farmer John 在他的农场上有 $N$ 头牛（$2 \le N \le 2 \cdot 10^5$），编号为 $1\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i, y_i)$（$1 \le x_i, y_i \le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！

其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求：

1. 两队都不能为空。
2. $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。
3. 存在一条无限长的网，放置为平面中非整数坐标的水平或垂直直线（例如 $x=0.5$、$y=2.5$），能将红队和蓝队完全分开。

帮帮农夫吧！计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。

输入格式

输入的第一行包含一个整数 $N$。

以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\ldots N$ 的一个排列，$y_i$ 类似。

输出格式

输出一个整数，为选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。

样例 1

输入

2
1 2
2 1

输出

2

样例说明

我们可以选择红队为牛 $1$、蓝队为牛 $2$，或者相反。无论哪种情况，都可以用网将两队分开（例如 $x=1.5$）。

样例 2

输入

3
1 1
2 2
3 3

输出

10

样例说明

以下是所有十种可能的分队方法（第 $i$ 个字符表示第 $i$ 头奶牛的归属：$R$=红队，$B$=蓝队，$.$=未入选）： $RRB$、$R.B$、$RB.$、$RBB$、$.RB$、$.BR$、$BRR$、$BR.$、$B.R$、$BBR$

样例 3

输入

3
1 1
2 3
3 2

输出

12

样例说明

以下是所有十二种可能的分队方法： $RRB$、$R.B$、$RBR$、$RB.$、$RBB$、$.RB$、$.BR$、$BRR$、$BR.$、$BRB$、$B.R$、$BBR$

样例 4

输入

40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40

输出

441563023

样例说明

确保输出答案对 $10^9+7$ 取模。

数据范围与提示

测试点	附加限制
5	$N \le 10$
6-9	$N \le 200$
10-13	$N \le 3000$
14-24	没有额外限制