#2567. 「APIO2016」划艇

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

在首尔城中,汉江横贯东西。在汉江的北岸,从西向东星星点点地分布着 NNN 个划艇学校,编号依次为 111NNN。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同,不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典,也可以选择不派出任何划艇参加。如果编号为 iii 的学校选择派出划艇参加庆典,那么,派出的划艇数量可以在 aia_iaibib_ibi 之间任意选择(aibi)。

值得注意的是,编号为 iii 的学校如果选择派出划艇参加庆典,那么它派出的划艇数量必须大于任意一所编号小于它的学校派出的划艇数量。

输入所有学校的 ai,bia_i, b_iai,bi 的值,求出参加庆典的划艇有多少种可能的情况,必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。

输入格式

第一行包括一个整数 NNN,表示学校的数量。
接下来 NNN 行,每行包括两个正整数,用来描述一所学校。其中第 iii 行包括的两个正整数分别表示 ai,bi(1≤ai≤bi≤109)a_i, b_i(1\le a_i\le b_i\le 10^9)ai,bi(1aibi109)

输出格式

输出一行,一个整数,表示所有可能的派出划艇的方案数除以 109+710^9+7109+7 得到的余数。

样例

样例输入

2
1 2
2 3

样例输出

7

样例解释

在只有一所学校派出划艇的情况下有 444 种方案,两所学校都派出划艇的情况下有 333 种方案,所以答案为 777

数据范围与提示

子任务 1(9 分):1≤N≤5001 \le N \le 5001N500 且对于所有的 1≤i≤N1 \le i \le N1iN,保证 ai=bia_i=b_iai=bi

子任务 2(22 分):1≤N≤5001 \le N \le 5001N500∑i=1N(bi−ai)≤106\sum_{i=1}^{N}(b_i-a_i) \le 10^6i=1N(biai)106

子任务 3(27 分):1≤N≤1001 \le N \le 1001N100

子任务 4(42 分):1≤N≤5001 \le N \le 5001N500