题目描述

在 $xy$ 平面上有 $2N$ 个球，第 $i$ 个球的位置为 $(x_i,\ y_i)$。这里，对于每个 $i$，$x_i,\ y_i$ 均为不小于 $1$ 且不大于 $N$ 的整数，且没有两个球处于同一位置。

Sune君为了收集这些球，准备了 $N$ 台 A 型机器人和 $N$ 台 B 型机器人。A 型机器人分别放置在 $(1,\ 0),\ (2,\ 0),\ ...,\ (N,\ 0)$，B 型机器人分别放置在 $(0,\ 1),\ (0,\ 2),\ ...,\ (0,\ N)$。

这两种类型的机器人启动时的动作如下：

• A 型机器人从 $(a,\ 0)$ 启动后，会回收直线 $x = a$ 上纵坐标 $y$ 最小的球并停止。如果该直线上没有球，则不进行操作直接停止。
• B 型机器人从 $(0,\ b)$ 启动后，会回收直线 $y = b$ 上横坐标 $x$ 最小的球并停止。如果该直线上没有球，则不进行操作直接停止。

每个机器人在停止后无法再次启动。在有机器人正在工作时，必须等其停下才能启动下一台机器人。

Sune君发现，机器人的启动顺序可能会导致无法收集全部的球。

在所有可能的 $(2N)!$ 种启动顺序中，能够收集所有球的有效顺序有多少种？请输出其对 $1,\!000,\!000,\!007$ 的余数。

输入格式

输入通过标准输入给出。

$N$ $x_1$ $y_1$ $...$ $x_{2N}$ $y_{2N}$

输出格式

输出能够收集所有球的机器启动顺序种数，结果对 $1,\!000,\!000,\!007$ 取余。

样例 1

输入

2
1 1
1 2
2 1
2 2

输出

8

样例 2

输入

4
3 2
1 2
4 1
4 2
2 2
4 4
2 1
1 3

输出

7392

样例 3

输入

4
1 1
2 2
3 3
4 4
1 2
2 1
3 4
4 3

输出

4480

样例 4

输入

8
6 2
5 1
6 8
7 8
6 5
5 7
4 3
1 4
7 6
8 3
2 8
3 6
3 2
8 5
1 5
5 8

输出

82060779

样例 5

输入

3
1 1
1 2
1 3
2 1
2 2
2 3

输出

0

说明/提示

限制

• $2 \le N \le 10^5$
• $1 \le x_i \le N$
• $1 \le y_i \le N$
• 对于 $i \ne j$，有 $x_i \ne x_j$ 或 $y_i \ne y_j$

样例解释 1

将放置在 $(1,0),\ (2,0)$ 的机器人分别记为 A1, A2，将放置在 $(0,1),\ (0,2)$ 的机器人分别记为 B1, B2。此时，满足条件的启动顺序共有如下 $8$ 种：

• A1, B1, A2, B2
• A1, B1, B2, A2
• A1, B2, B1, A2
• A2, B1, A1, B2
• B1, A1, B2, A2
• B1, A1, A2, B2
• B1, A2, A1, B2
• B2, A1, B1, A2

因此输出 $8$。

样例解释 5

如果不存在满足条件的启动顺序，则输出 $0$。

由 ChatGPT 5 翻译