Description

“川桑，家乡的樱花开了。”
川桑原本是皇室成员，亿万富翁，但是，因为那次网恋，他付出了一切。
网恋一共持续了\(n\)天，第\(i\)天，他既可以选择和女孩视频，也可以选择给女孩打钱，且第\(i\)天如果要打钱，那么打的钱数必须是\([l_i,r_i]\)范围内的整数。
人不能越活越穷酸，那样会被看不起，所以每次打钱的数目都必须高于上次打钱的数目。
那么川桑一共有多少种打钱的方案，两个方案不同，当且仅当某一天打钱的数目不同，选择和女孩视频的日子看作打了\(0\)元钱。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个正整数\(n\)，表示网恋的持续天数。\((1<=n<=500)\)
接下来\(n\)行，每行两个整数\(l_i,r_i(1<=l_i<=r_i<=10^9)\)，表示第\(i\)天打钱的范围限制。

Output

输出一行一个整数，为答案除以\(1000000007\)所得余数。

Sample 1

Input

2
1 2
2 3

Output

8

Limitation

1s, 1GB for each test case.

Source

wbs