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

时间限制：$6\mathtt{\text{s}}$

空间限制：$1024\mathtt{\text{MB}}$

下载

样例数据下载