配点 : $1400$ 点

問題文

$2N$ 枚のカードと $N$ 個の箱があります。 カードには $1$ から $2N$ までの番号が付いており、箱には $1$ から $N$ までの番号が付いています。 カードは各箱に $2$ 枚ずつ入っています。箱 $i$ にはカード $A_i$ とカード $B_i$ が入っています。

この $N$ 個の箱を一列に並べる方法であって、以下の条件を満たす並べ方の個数を $10^9+7$ で割った余りを求めてください。

• 箱を左から順に開けていき、入っている $2$ 枚のカードを末尾に好きな順で並べていくことで、長さ $2N$ のカードの列が得られる。左から $j$ 番目のカードの番号を $P_j$ とする。このとき、カードをうまく並べることで、数列 $P_1,P_2,\ldots, P_{2N}$ におけるピークの個数が $N-1$ となる。

ただし、数列 $P_1,P_2,\ldots, P_{2N}$ におけるピークとは、 $2 \leq j < 2N$ なる整数 $j$ であって $P_{j-1} < P_j$ かつ $P_j > P_{j+1}$ となるものを指します。

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i, B_i \leq 2N$
• $A_1,\ldots,A_N,B_1,\ldots,B_N$ は相異なる。

入力

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

$N$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

出力

答えを出力せよ。

3
1 3
2 4
5 6

4

例えば、箱 $1,2,3$ をこの順で並べたとき、 以下のようにカードを並べることで、数列 $P$ のピークの個数が $2$ となります。

• まず箱 $1$ に入っているカードをカード $1,3$ の順で並べる。
• 次に箱 $2$ に入っているカードをカード $2,4$ の順で末尾に並べる。
• 最後に箱 $3$ に入っているカードをカード $6,5$ の順で末尾に並べる。

このとき、数列 $P$ は $(1,3,2,4,6,5)$ となり $j=2,5$ がピークとなります。

6
5 8
7 2
1 3
11 6
4 12
9 10

492

10
20 15
8 5
6 7
4 9
13 1
11 14
10 17
19 12
3 16
2 18

1411200