UOJ Logo Universal Online Judge

UOJ

#356. 【JOI2017春季合宿】Port Facility

统计

小M有两个本质不同的栈。

无聊的小M找来了$n$个玩具。之后小M把这$n$个玩具随机顺序加入某一个栈或把他们弹出。

现在小M告诉你每个玩具的入栈和出栈时间,现在她想考考小S,有多少种方案,把每个玩具分配给两个栈之一,并且存在一种满足小M告诉你的入栈和出栈时间的入栈序列。

可怜的小S当然不知道啦,所以他求助于你。

输入格式

第一行一个整数$n$。

接下来$n$行,每行两个整数$l_i,r_i$,表示第$i$个玩具的入栈和出栈时间。

输出格式

一行一个整数,表示答案对$10^9+7$取模的值

样例一

input

4
1 3
2 5
4 8
6 7

output

4

样例二

input

3
1 4
2 5
3 6

output

0

样例三

input

5
1 4
2 10
6 9
7 8
3 5

output

8

样例四

input

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

output

16

限制与约定

对于所有数据,

$1\le n\le 10^6,1\le l_i < r_i \le 2n$,$l_i,r_i$互不相同。

子任务 分值 $n$
1 10 $\le 20$
2 12 $\le 2000$
3 56 $\le 10^5$
4 22 $\le 10^6$

时间限制:$4\texttt{s}$

空间限制:$1024\texttt{MB}$

下载

样例数据下载