Description

Little R likes studying robots.

Recently, Little R developed two new types of robots, P-type robots and Q-type robots. Now he wants to test their moving abilities. The test is done on $n$ pillars arranged in a line from left to right, numbered $1 - n$ in order. The height of pillar $i$ is a positive integer $h_i$. Robots can only move between adjacent pillars, that is: if a robot is currently on pillar $i$, it can only try to move to pillar $i - 1$ and pillar $i + 1$.

In each test, Little R chooses a starting point $s$ and places both types of robots on pillar $s$. Then they move according to their own rules.

The P-type robot keeps moving to the left, but it cannot move onto a pillar that is higher than the starting pillar $s$. More specifically, the P-type robot stops at pillar $l \ (l \leq s)$ if and only if both of the following conditions hold:

• $l = 1$ or $h_{l-1} > h_s$.

• For every $j$ with $l \leq j \leq s$, we have $h_j \leq h_s$.

The Q-type robot keeps moving to the right, but it can only move onto pillars that are lower than the starting pillar $s$. More specifically, the Q-type robot stops at pillar $r \ (r \geq s)$ if and only if both of the following conditions hold:

• $r = n$ or $h_{r+1} \geq h_s$.

• For every $j$ with $s < j \leq r$, we have $h_j < h_s$.

Now, Little R can set the height of each pillar. The selectable height range for pillar $i$ is $[A_i, B_i]$, that is, $A_i \leq h_i \leq B_i$. Little R hopes that no matter where the test starting point $s$ is chosen, the absolute value of the difference between the numbers of pillars moved over by the two robots is always less than or equal to $2$. He wants to know how many height-setting schemes satisfy this requirement. Little R considers two schemes different if and only if there exists some $k$ such that the height of pillar $k$ is different in the two schemes. Please output the number of valid schemes modulo $10^9 + 7$.

Input Format

The first line contains a positive integer $n$, representing the number of pillars.

The next $n$ lines each contain two positive integers $A_i, B_i$, representing the minimum and maximum height of pillar $i$.

Output Format

Output one line with one integer, the answer modulo $10^9 + 7$.

5
3 3
3 3
3 4
2 2
3 3

1

Hint

More Samples

You can get more samples through the additional files.

Sample 2

See robot/robot2.in and robot/robot2.ans in the additional files.

Sample 3

See robot/robot3.in and robot/robot3.ans in the additional files.

Sample 4

See robot/robot4.in and robot/robot4.ans in the additional files.

Explanation for Sample 1

There are two possible pillar height settings:

• Heights: 3 2 3 2 3. If the starting point is set to $5$, the P-type robot will stop at pillar $1$, moving across $4$ pillars. The Q-type robot stops at pillar $5$, moving across $0$ pillars. This does not satisfy the condition.

• Heights: 3 2 4 2 3. In this case, no matter where the starting point is chosen, the condition is satisfied. Details are shown in the table below:

::cute-table{tuack}

Constraints

For all testdata: $1 \leq n \leq 300$, $1 \leq A_i \leq B_i \leq 10^9$.

The detailed limits for each test point are shown in the table below:

::cute-table{tuack}

Translated by ChatGPT 5