[USACO24JAN] Mooball Teams III P

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 想要挑选两支队伍来玩哞球游戏！ 其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。唯一的其他要求是基于哞球独特的特点：一个无限长的网，必须将其放置为平面中非整数坐标的水平或垂直直线，例如 $x=0.5$。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。 帮帮农夫吧！为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。 ## Input 输入的第一行包含一个整数 $N$。 以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\ldots N$ 的一个排列，$y_i$ 类似。 ## Output 输出一个整数，为选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。 [samples] ## Note ### 样例解释 1 我们可以选择红队为牛 1，蓝队为牛 2，或者相反。无论哪种情况，我们都可以用一个网将两支球队分开（例如，$x=1.5$）。 ### 样例解释 2 以下是所有的十种可能的将奶牛分队的方法；第 $i$ 个字符表示第 $i$ 头奶牛的队伍，`R` 表示红队，`B` 表示蓝队，或 `.` 表示第 $i$ 头奶牛不在一个队伍中。 ```plain RRB R.B RB. RBB .RB .BR BRR BR. B.R BBR ``` ### 样例解释 3 以下是所有的十二种可能的将奶牛分队的方法： ```plain RRB R.B RBR RB. RBB .RB .BR BRR BR. BRB B.R BBR ``` ### 样例解释 4 确保输出答案对 $10^9+7$ 取模。 ### 测试点性质 - 测试点 $5$：$N\le 10$。 - 测试点 $6-9$：$N\le 200$。 - 测试点 $10-13$：$N\le 3000$。 - 测试点 $14-24$：没有额外限制。