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\le s)$, if and only if:

• $l=1$ or $h_{l-1}>h_s$
• $h_j\le h_s$ holds for all $l\le j\le 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\ge s)$, if and only if:

• $r=n$ or $h_{r+1}\ge h_s$
• $h_j<h_s$ holds for all $s<j\le 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\le n\le 300$, $1\le A_i\le B_i\le {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\le 10000$
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