There are two robots ~P~ and ~Q~ and now we are going to run some experiments on them.

There are ~n~ pillars on a row numbered from ~1~ to ~n~ and the height of each pillar ~i~ is a positive integer ~h_i~. Both robots can move from one to its neighbors, which means if the robot is now at pillar ~i~, it can only try moving to ~i-1~ or ~i+1~.

In each experiment, we will pick a starting pillar ~s~ and put two robots on it. Two robots will then move under certain rules:

Robot ~P~ will always move to the left, but it can't move to the pillars that are higher than pillar ~s~. Formally, it will stop at pillar ~l,(l \leq s)~ if and only if:

• ~l = 1~ or ~h_{l-1} > h_s~
• ~h_j \leq h_s~ holds for all ~l \leq j \leq s~

Robot ~Q~ will always move to the right, but it can only move to the pillars that are shorter than pillar ~s~. Formally, it will stop at pillar ~r,(r \geq s)~ if and only if:

• ~r = n~ or ~h_{r+1} \geq h_s~
• ~h_j < h_s~ holds for all ~s < j \leq r~

Now for each pillar ~i~, we can choose its height to be any integer in ~[A_i,B_i]~. We hope that no matter which pillar we choose as the starting pillar ~s~, the absolute difference between ~P~ and ~Q~'s moving distance (i.e. the number of pillars one robot has gone through) is not larger than ~2~.

Please calculate the number of plans to choose pillars' height satisfying the above condition. We consider two plans to be different if there exists a pillar ~k~ that has different height in those two plans. Since the answer may be large, please output the answer modulo ~10^9+7~.

Input Specification

The first line contains an integer ~n~, indicating the number of pillars.

In the following ~n~ lines, each line contains two integers ~A_i, B_i~.

Constraints

For all test cases, ~1 \leq n \leq 300, 1 \leq A_i \leq B_i \leq 10^9~.

Test Case	~n \le~	Others
1, 2	~7~	~A_i = B_i, B_i \le 7~
3, 4		~B_i \le 7~
5, 6, 7	~50~	~B_i \le 100~
8, 9, 10	~300~	~B_i \leq 10\,000~
11, 12	~50~	~A_i = 1, B_i = 10^9~
13, 14, 15		None
16, 17	~150~
18, 19	~200~
20	~300~

Output Specification

Output one integer on one line, the answer modulo ~10^9+7~.

Sample Input 1

5
3 3
2 2
3 4
2 2
3 3

Sample Output 1

1

---