题目描述

小明喜欢刮刮刮乐，刮刮乐是一种彩票，刮开以后会随机获得奖金。

小明买了$n$张刮刮乐，其中第$i$张刮刮乐的获奖金额$x_i$是一个$[l_i,r_i]$间的随机整数。

那么，对于小明来说，他刮开这$n$张刮刮乐的获奖情况就一共有$\prod_{i=1}^n (r_i-l_i+1)$种情况。

当小明开出大奖的时候，他就会开心，所以他定义他最终的开心程度是所有刮刮乐开出奖金的最大值，也就是$\max_{i=1}^n x_i$。

小明现在比较好奇，他刮完这些彩票以后期望的开心程度是多少，但是PION不让考期望，所以请你计算所有情况下小明的开心程度之和。

输入格式

第一行输入$n$。

接下来$n$行，每行输入$l_i,r_i$。

输出格式

一个数字表示答案$mod\ 10^9+7$。

样例输入 #1

3
1 2
1 2
1 2

样例输出 #1

15

样例解释 #1

一共$8$种情况，只有$(1,1,1)$的开心程度是$1$，其他都是$2$，所以答案是$1+2\times 7=15$。

样例输入 #2

6
1 1005
12 1145
55 5555
11 1111
121 212
1 2525

样例输出 #2

99518744

数据范围

对于30%的数据：$n\leq 5,r_i\leq 10$。

对于50%的数据：$n\leq 100,r_i\leq 100$。

对于75%的数据：$n\leq 3000,r_i\leq 10^4$。

对于100%的数据：$n\leq 10^6,1\leq l_i\leq r_i\leq 10^6,∑(r_i-l_i+1)\leq 10^8$。