题目描述

$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}$ となるものを指します。

输入格式

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

$N$ $A_1$ $B_1$ $:$ $A_N$ $B_N$

输出格式

答えを出力せよ。

题目大意

有 $2n$ 张卡牌与 $n$ 个盒子。卡牌被编号为 $1$ 至 $2n$，盒子被编号为 $1$ 至 $n$。每个盒子里放着两张卡牌：第 $i$ 个盒子里放着编号为 $A_i$ 和 $B_i$ 的卡牌。

找到满足下述条件的排列盒子的方案数：

• 考虑通过以下的方式取得长为 $2n$ 的卡牌序列：从左到右考虑每个盒子，从其中拿出两张卡牌，以任意方式放置于当前序列尾。条件即为所得到的序列 $P_1,P_2,\cdots,P_{2n}$ 有 $n-1$ 个峰。

一个长为 $n$ 的序列 $p = \{p_1, p_2,\cdots,p_n\}$ 的其中一个峰为整数 $1 <i<n$，满足 $p_{i-1} < p_i$ 且 $p_i > p_{i + 1}$。

答案对 $10^9 + 7$ 取模。

$n\le 2\times 10^5,\ 1\le A_i,B_i\le 2n$。

3
1 3
2 4
5 6

4

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

提示

制約

• $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$ は相異なる。

Sample Explanation 1

例えば、箱 $1,2,3$ をこの順で並べたとき、 以下のようにカードを並べることで、数列 $P$ のピークの個数が $2$ となります。 - まず箱 $1$ に入っているカードをカード $1,3$ の順で並べる。 - 次に箱 $2$ に入っているカードをカード $2,4$ の順で末尾に並べる。 - 最後に箱 $3$ に入っているカードをカード $6,5$ の順で末尾に並べる。 このとき、数列 $P$ は $(1,3,2,4,6,5)$ となり $j=2,5$ がピークとなります。