题目描述

我们有 $2N$ 张卡片和 $N$ 个盒子。卡片编号为 $1$ 到 $2N$，盒子编号为 $1$ 到 $N$。每个盒子中有两张卡片；盒子 $i$ 中包含卡片 $A_i$ 和卡片 $B_i$。

求满足以下条件的将 $N$ 个盒子排成一行的方式数（结果对 $(10^9+7)$ 取模）：

• 按照以下步骤获得一个 $2N$ 张卡片的序列：从左到右依次打开每个盒子，并按照我们喜欢的顺序将其中的两张卡片添加到序列的末尾。以这种方式，可以得到一个具有 $N-1$ 个峰值的序列 $P_1,P_2,\\ldots, P_{2N}$。

在这里，序列 $P_1,P_2,\\ldots, P_{2N}$ 中的峰值是指满足 $2 \\leq j < 2N$ 且 $P_{j-1} < P_j$ 且 $P_j > P_{j+1}$ 的整数 $j$。

约束条件

• $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$

输出

输出答案。

示例输入 1

3
1 3
2 4
5 6

示例输出 1

4

例如，如果我们按照这个顺序排列盒子 $1, 2, 3$，我们可以按照以下方式排列卡片，得到一个具有 $2$ 个峰值的序列 $P$：

• 首先，按顺序排列盒子 $1$ 中的卡片 $1, 3$；
• 接下来，按顺序将盒子 $2$ 中的卡片追加到末尾，得到 $2, 4$；
• 最后，按顺序将盒子 $3$ 中的卡片追加到末尾，得到 $6, 5$。

在这里，我们有 $P=(1,3,2,4,6,5)$，具有峰值 $j=2,5$。

示例输入 2

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

示例输出 2

492

示例输入 3

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

示例输出 3

1411200