#P7385. [2019雅礼集训]第三日

    ID: 7399 传统题 4000ms 440MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>图论数据结构动态规划CF2600线段树二分图

[2019雅礼集训]第三日

第三日

题目描述

创造第三日,因为神威作为超级计算机,不懂得OIER的生活习性,于是创造了Hack国国王·肥克泵 ·zjb_shadow·骇客十字星,赋予了他改造大陆的权限肥克说,我需要领土,于是他占据了X503的东南部肥克说,大陆需要权量对错,于是他命名这个国家为Hack国,只有有效Hack记录达到20时才能得到这个国家的国籍肥克说,大陆需要和外界的交流,于是他打通了X503通向百度之星的道路肥克说,大陆需要强者支配弱者,于是肥克开始天天虐狗肥克准备在跟他的网恋男友聊天之前再写一篇题解,于是他打开了洛谷上的双栈排序,并留下了一篇优质的题解但是肥克觉得这是个傻逼题,于是把它加强成了一个计数题,题目意思如下: 你有两个不同的栈,以及 nn 个数。已知第 ii 个数的入栈时间 xix_i 和出栈时间 yiy_i,其中 xi<yix_i<y_i。每个数入栈时选择其中一个栈,出栈时必须从这个栈的栈顶取出。

求有多少种合法的操作序列。两个栈有区别,选择不同的栈视为不同方案。答案对 109+710^9+7 取模。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个数的入栈和出栈时间。保证 xi<yix_i<y_i,所有 2n2n 个时间互不相同。时间可以是任意整数,仅相对先后顺序影响答案,不要求取值为 11 到 2n2n。

输出格式

输出一个整数,表示合法方案数量对 109+710^9+7 取模的结果。

样例输入1

4
1 3
2 5
4 8
6 7

样例输出1

4

样例输入2

3
1 4
2 5
3 6

样例输出2

0

样例输入3

5
1 4
2 10
6 9
7 8
3 5

样例输出3

8

数据范围

数据比例 附加限制
10%10\% n≤20n\le20
20%20\% n≤2000n\le2000
70%70\% n≤105n\le10^5
100%100\% 1≤n≤1061\le n\le10^6