Problem Statement

Suppose a sequence of "real numbers" $a_1,\ldots,a_N$ of length $N$ is constructed by the following method. Find the probability that the constructed sequence is a Kadomatsu sequence.

• Choose a "real number" between $A_i$ and $B_i$, inclusive, uniformly at random, and let it be $a_i$.

A sequence $a_1,\ldots,a_N$ is called a Kadomatsu sequence if $a_1 \le a_2 \ge a_3 \le a_4 \ge a_5 \le \cdots $. That is, the following holds for all $1 \le i \le N-1$.

• If $i$ is odd, then $a_i \le a_{i+1}$.
• If $i$ is even, then $a_i \ge a_{i+1}$.

Note that the constructed sequence is not an integer sequence but a "real sequence".

Input

$N$
$A_1\ B_1$
$\vdots$
$A_N\ B_N$

$3 \le N \le 200$
$1 \le A_i < B_i \le 10^9$
All inputs are integers.

Output

The answer can be expressed as an irreducible fraction $p/q$, so output $p\,q^{-1} \bmod{10^9+7}$. That is, output the smallest non-negative integer $x$ satisfying $xq \equiv p \pmod{10^9+7}$. In this problem, this value always exists.

Sample

3
1 3
1 3
1 3

333333336

3
1 2
2 3
1 2

1

3
2 3
1 2
2 3

0

5
1 4
2 3
1 3
2 4
1 4

715740746

9
766526787 974319581
941243410 942612052
427056305 964028266
313356130 664522966
480128631 531723103
1626524 615851774
293907611 496577233
1955784 467846274
83687962 802560435

175278186