AT_arc083_d.[ARC083F] Collecting Balls

在 $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$ 取余。

限制

• $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 翻译