配点: $1200$ 点

問題文

$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$ で割った余りを求めてください。

制約

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

入力

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

$N$

$x_1$ $y_1$

$...$

$x_{2N}$ $y_{2N}$

出力

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

2
1 1
1 2
2 1
2 2

8

位置 $(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$ を出力します。

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

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