#arc083d. [arc083_d]Collecting Balls

[arc083_d]Collecting Balls

题目描述

xyxy 平面上有 2N2N 个球。它们的坐标分别为 (xi,yi)(x_i, y_i)。这里,xix_iyiy_i 对于所有 ii 都是介于 11NN(包含)的整数,并且没有两个球占据相同的坐标。

为了收集这些球,Snuke 准备了 2N2N 个机器人,其中 NN 个是 A 型机器人,NN 个是 B 型机器人。然后,他将类型 A 的机器人放置在坐标 (1,0),(2,0),...,(N,0)(1, 0), (2, 0), ..., (N, 0) 处,将类型 B 的机器人放置在坐标 (0,1),(0,2),...,(0,N)(0, 1), (0, 2), ..., (0, N) 处,每个位置放置一个。

激活时,每种类型的机器人会按照以下方式运行。

  • 当一个类型 A 的机器人在坐标 (a,0)(a, 0) 处被激活时,它会移动到线段 x=ax = a 上最低 yy 坐标的球所在的位置,收集该球并停止工作。如果没有这样的球,它将不做任何操作而停止工作。

  • 当一个类型 B 的机器人在坐标 (0,b)(0, b) 处被激活时,它会移动到线段 y=by = b 上最低 xx 坐标的球所在的位置,收集该球并停止工作。如果没有这样的球,它将不做任何操作而停止工作。

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

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

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

约束条件

  • 2N1052 \leq N \leq 10^5
  • 1xiN1 \leq x_i \leq N
  • 1yiN1 \leq y_i \leq N
  • iji ≠ j,则要么 xixjx_i ≠ x_j,要么 yiyjy_i ≠ y_j

输入格式

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

NN x1x_1 y1y_1 ... x2Nx_{2N} y2Ny_{2N}

输出格式

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


示例输入1

2
1 1
1 2
2 1
2 2

示例输出1

我们将放置在 (1,0)(1, 0)(2,0)(2, 0) 处的机器人分别称为 A1 和 A2,将放置在 (0,1)(0, 1)(0,2)(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

因此,输出应为 88


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

当没有满足条件的激活顺序时,输出应为 00