B. Sequences
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$N$$$ integer intervals $$$[L_i, R_i]$$$, in a fixed order. For each index $$$i$$$, exactly one integer $$$x_i$$$ belonging to the $$$i$$$-th interval must be chosen, that is, $$$L_i \leq x_i \leq R_i$$$.

A choice is valid if the sequence $$$x_1, x_2, \dots, x_N$$$ is strictly increasing, that is, if $$$x_1 \lt x_2 \lt \dots \lt x_N$$$. Two choices are considered distinct if they differ in at least one value $$$x_i$$$.

Compute the number of valid choices, modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 300$$$).

Each of the following $$$N$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq 10^{9}$$$), describing the $$$i$$$-th interval.

Output

Print a single integer: the number of valid choices, modulo $$$10^9 + 7$$$.

Example
Input
3
2 4
1 4
1 5
Output
4
Note

Explanation for example 1

The four valid sequences are $$$(2, 3, 4)$$$, $$$(2, 3, 5)$$$, $$$(2, 4, 5)$$$, and $$$(3, 4, 5)$$$. Therefore, the answer is $$$4$$$.