题目描述

$xy$ 平面上に $2N$ 個のボールがあります。このうち $i$ 番目のボールの位置は $(x_i,\ y_i)$ です。 ここで、すべての $i$ について $x_i,\ y_i$ は $1$ 以上 $N$ 以下の整数であり、$2$ つ以上のボールが同じ位置にあることはありません。

すぬけ君は、これらのボールを回収するために、タイプ A, B のロボットを $N$ 台ずつ用意し、 位置 $(1,\ 0),\ (2,\ 0),\ ...,\ (N,\ 0)$ にタイプ A のロボットを、位置 $(0,\ 1),\ (0,\ 2),\ ...,\ (0,\ N)$ にタイプ B のロボットをそれぞれ $1$ 台ずつ設置しました。

それぞれのタイプのロボットは起動されると以下のように動作します。

• タイプ A のロボットは、位置 $(a,\ 0)$ で起動されると、直線 $x\ =\ a$ 上にあるボールのうち $y$ 座標の値が最小のものを回収して停止する。そのようなボールが存在しない場合は何もせずに停止する。
• タイプ B のロボットは、位置 $(0,\ b)$ で起動されると、直線 $y\ =\ b$ 上にあるボールのうち $x$ 座標の値が最小のものを回収して停止する。そのようなボールが存在しない場合は何もせずに停止する。

一度停止したロボットをもう一度起動することはできません。また、動作中のロボットがある場合、それが停止するまで新たなロボットを起動することはできません。

すぬけ君は、ロボットを起動しようとして、起動する順序によってはすべてのボールを回収することができない可能性があることに気づきました。

ロボットを起動する順序として考えられる $(2N)!$ 通りのうち、すべてのボールを回収できるような順序の個数を $1,000,000,007$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

すべてのボールを回収できるようなロボットの起動順序の個数を $1,000,000,007$ で割った余りを出力せよ。

题目大意

$n\times n$ 的正方形上有 $2n$ 个小球，第 $i$ 个在 $(x_i,y_i)$。

有 $n$ 个 A 类机器人，第 $i$ 个在 $(0,i)$，有 $n$ 个 B 类机器人，第 $i$ 个在 $(i,0)$。

启动一个 A 类机器人后，它会向右走，将碰到的第一个球收集起来，并返回起点。启动一个 B 类机器人后，它会向上走，将碰到的第一个球收集起来，并返回起点。

只有上一个机器人返回起点后，下一个机器人才会被启动。机器人一旦被使用过一次就不能被再次使用。

问你有多少种启动机器人的顺序，能够收集完所有小球。方案数对 $10^9+7$ 取模 。

$n\leq 10^5$

2
1 1
1 2
2 1
2 2

8

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

7392

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

4480

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

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

0

提示

制約

• $2\ ≦\ N\ ≦\ 10^5$
• $1\ ≦\ x_i\ ≦\ N$
• $1\ ≦\ y_i\ ≦\ N$
• $i\ ≠\ j$ のとき、$x_i\ ≠\ x_j$ または $y_i\ ≠\ y_j$

Sample Explanation 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$ を出力します。

Sample Explanation 5

条件を満たす順序が存在しない場合、答えは $0$ となります。