分数: 1400 点
问题陈述
我们有 2N 卡片和 N 盒。 卡片已编号 1 通过 2N,并且盒子已编号 1 通过 N。 每个盒子包含两张卡片;盒子 i 包含卡 A_i 和卡 B_i.
查找,取模 (10^9+7),排列方式的数量 N 框连续满足以下条件。
- 考虑获取一系列 2N 卡片如下:对于每个盒子,从左到右,打开它,并将其中的两张卡片按照我们喜欢的顺序附加到序列的末尾。这样就可以得到一个序列 P_1,P_2,\ldots, P_{2N} 与 N-1 峰值。
这里,序列中的峰值 P_1,P_2,\ldots, P_{2N} 是一个整数 j 满意 2 \leq j < 2N 这样 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
输出
打印答案。
示例输入 1
3 1 3 2 4 5 6
示例输出 1
4
例如,如果我们排列盒子 1, 2, 3 按照这个顺序,我们可以将卡片排列如下,得到一个序列 P 与 2 峰值:
- 首先,将卡片放入盒子中 1 顺序 1, 3;
- 接下来,将卡片附加到 Box 中 2 位于订单末尾 2, 4;
- 最后,将卡片附加到Box中 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