← 返回题目列表

AtCoder · agc053_e

E. 更多的山峰更多的乐趣

中文机器翻译题面 查看原题

分数: 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