题目描述

在 $xy$ 平面上有 $2N$ 个球。它们的坐标分别为 $(x_i, y_i)$。这里，$x_i$ 和 $y_i$ 对于所有 $i$ 都是介于 $1$ 到 $N$（包含）的整数，并且没有两个球占据相同的坐标。

为了收集这些球，Snuke 准备了 $2N$ 个机器人，其中 $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$ 坐标的球所在的位置，收集该球并停止工作。如果没有这样的球，它将不做任何操作而停止工作。

一旦停止工作，机器人就不能再次被激活。而且，在一个机器人正在工作时，不能激活新的机器人，直到该机器人停止工作。

当 Snuke 准备激活一个机器人时，他注意到，根据机器人激活的顺序，他可能无法收集到所有的球。

在 $(2N)!$ 种可能的机器人激活顺序中，找出满足所有球都能够被收集的顺序的数量，对 $1,000,000,007$ 取模。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq x_i \leq N$
• $1 \leq y_i \leq N$
• 若 $i ≠ j$，则要么 $x_i ≠ x_j$，要么 $y_i ≠ y_j$。

输入格式

输入以以下格式从标准输入给出：

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

输出格式

输出满足所有球都能够被收集的机器人激活顺序的数量，对 $1,000,000,007$ 取模。

示例输入1

2
1 1
1 2
2 1
2 2

示例输出1

8

我们将放置在 $(1, 0)$ 和 $(2, 0)$ 处的机器人分别称为 A1 和 A2，将放置在 $(0, 1)$ 和 $(0, 2)$ 处的机器人分别称为 B1 和 B2。有八种满足条件的激活顺序，如下所示：

• 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$。

示例输入2

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

示例输出2

7392

示例输入3

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

示例输出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

示例输出4

82060779

示例输入5

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

示例输出5

0

当没有满足条件的激活顺序时，输出应为 $0$。