Robot

Two robots, $P$ and $Q$, take part in a series of experiments. There are $n$ pillars in a row, numbered 1 to $n$, and the height of pillar $i$ is a positive integer $h_i$. Each robot moves only to a neighboring pillar. A robot on pillar $i$ can only try to move to pillar $i-1$ or $i+1$. In each experiment, you choose a starting pillar $s$ and place both robots on it. Then the robots move by the rules below. Robot $P$ always moves left, but it cannot move onto a pillar higher than pillar $s$. Precisely, $P$ stops at pillar $l$ ($l \le s$) if and only if $l = 1$ or $h_{l-1} > h_s$, and $h_j \le h_s$ for all $l \le j \le s$. Robot $Q$ always moves right, but it can only move onto pillars shorter than pillar $s$. Precisely, $Q$ stops at pillar $r$ ($r \ge s$) if and only if $r = n$ or $h_{r+1} \ge h_s$, and $h_j < h_s$ for all $s < j \le r$. The height of each pillar $i$ can be any integer from $A_i$ to $B_i$, inclusive. For every choice of starting pillar $s$, the absolute difference between the number of pillars that $P$ and $Q$ pass through must be at most 2. Count the height assignments that satisfy this for every $s$. Two assignments differ if some pillar $k$ has a different height in them. Output the count modulo $10^9+7$.

The first line contains $n$. Each of the next $n$ lines contains two integers $A_i$ and $B_i$.

Print one integer on one line, the answer modulo $10^9+7$.

$1 \le n \le 300$ and $1 \le A_i \le B_i \le 10^9$.