题目描述

有 $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$，且 $P_{j-1}<P_j$ 且 $P_j>P_{j+1}$ 的整数 $j$。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出满足条件的排列方案数。

样例 1

输入

3
1 3
2 4
5 6

输出

4

样例 2

输入

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

输出

492

样例 3

输入

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$ 互不相同。

样例解释 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$ 是峰值。

由 ChatGPT 4.1 翻译