在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着 $N$ 个划艇学校，编号依次为 $1$ 到 $N$。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同，不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典，也可以选择不派出任何划艇参加。如果编号为 $i$ 的学校选择派出划艇参加庆典，那么，派出的划艇数量可以在 $a_i$ 至 $b_i$ 之间任意选择（$a_i \leq b_i$）。

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

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

输入格式

第一行包括一个整数 $N$，表示学校的数量。

接下来 $N$ 行，每行包括两个正整数，用来描述一所学校。其中第 $i$ 行包括的两个正整数分别表示 $a_i,b_i（1 \leq a_i \leq b_i \leq 10^9）$。

输出格式

输出一行，一个整数，表示所有可能的派出划艇的方案数除以 $1,000,000,007$ 得到的余数。

2
1 2
2 3

7

在只有一所学校派出划艇的情况下有 $4$ 种方案，两所学校都派出划艇的情况下有 $3$ 种方案，所以答案为 $7$。

限制与约定

子任务 $1$（$9$ 分）：$1 \leq N \leq 500$ 且对于所有的 $1 \leq i \leq N$，保证 $a_i=b_i$。

子任务 $2$（$22$ 分）：$1 \leq N \leq 500$ 且 $\sum_{i=1}^N (b_i-a_i) \leq 10^6$。

子任务 $3$（$27$ 分）：$1 \leq N \leq 100$。

子任务 $4$（$42$ 分）：$1 \leq N \leq 500$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载