Little R likes to study robots.

Recently, Little R has developed two types of robots: type P and type Q. He now wants to test the mobility of these two types of robots. The test is conducted on $n$ pillars arranged in a row from left to right, numbered $1 \sim n$. The height of pillar $i$ is a positive integer $h_i$. Robots can only move between adjacent pillars, meaning if a robot is currently on pillar $i$, it can only attempt to move to pillar $i-1$ or pillar $i+1$.

In each test, Little R selects a starting point $s$ and places both robots on pillar $s$. They then move according to their own rules.

Type P robots always move to the left, but they cannot move to a pillar higher than the starting point $s$. More specifically, a type P robot stops at pillar $l$ ($l \le s$) if and only if the following two conditions are met: $l = 1$ or $h_{l-1} > h_s$. For all $j$ such that $l \le j \le s$, $h_j \le h_s$.

Type Q robots always move to the right, but they can only move to a pillar lower than the starting point $s$. More specifically, a type Q robot stops at pillar $r$ ($r \ge s$) if and only if the following two conditions are met: $r = n$ or $h_{r+1} \ge h_s$. For all $j$ such that $s < j \le r$, $h_j < h_s$.

Now, Little R can set the height of each pillar. The height of pillar $i$ can be chosen from the range $[A_i, B_i]$, i.e., $A_i \le h_i \le B_i$. Little R hopes that no matter where the starting point $s$ is chosen, the absolute difference between the number of pillars moved by the two robots is less than or equal to 2. He wants to know how many ways to set the pillar heights satisfy this requirement. Two schemes are considered different if and only if there exists a $k$ such that the height of pillar $k$ is different in the two schemes. Please tell him the number of valid schemes modulo $10^9 + 7$.

Input

The first line contains a positive integer $n$, representing the number of pillars. The next $n$ lines each contain two positive integers $A_i$ and $B_i$, representing the minimum and maximum height of pillar $i$, respectively.

Output

A single integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

5
3 3
3 3
3 4
2 2
3 3

Output 1

1

Note 1

There are two possible height configurations: 1. Heights: 3 2 3 2 3. If the starting point is set at 5, the type P robot will stop at pillar 1, having moved across 4 pillars. The type Q robot stops at pillar 5, having moved across 0 pillars. This does not satisfy the condition. 2. Heights: 3 2 4 2 3. In this case, the condition is satisfied regardless of the starting point.

Constraints

For all test data: $1 \le n \le 300$, $1 \le A_i \le B_i \le 10^9$.