Description

In the city of Seoul, the Han River runs east to west. On its north bank, from west to east, there are $N$ rowing schools, numbered $1$ to $N$. Each school owns several boats. All boats from the same school share the same color, and different schools have different colors. Boats of the same color are considered identical. Each school may choose to send some boats to the festival, or choose not to send any. If school $i$ chooses to participate, it may send any number of boats between $a_i$ and $b_i$ inclusive ($a_i \leq b_i$).

Importantly, if school $i$ participates, the number of boats it sends must be greater than the number sent by any participating school with a smaller index.

Given all $a_i$ and $b_i$, determine how many possible participation configurations there are, with at least one boat participating. Two configurations are different if and only if there exists some color (i.e., some school) for which the number of participating boats differs.

Input Format

The first line contains an integer $N$, the number of schools.

The next $N$ lines each describe one school. Line $i$ contains two positive integers $a_i$ and $b_i$ ($1 \leq a_i \leq b_i \leq 10^9$).

Output Format

Output a single line with one integer: the number of possible configurations modulo $1{,}000{,}000{,}007$.

2
1 2
2 3

7

Hint

Sample explanation:

• When only one school participates, there are $4$ configurations.
• When both schools participate, there are $3$ configurations.
• Therefore, the answer is $7$.

Constraints:

• Subtask $1$ (9 points): $1 \leq N \leq 500$ and $a_i = b_i$ for all $1 \leq i \leq N$.
• Subtask $2$ (22 points): $1 \leq N \leq 500$ and $\sum_{i=1}^N (b_i - a_i) \leq 10^6$.
• Subtask $3$ (27 points): $1 \leq N \leq 100$.
• Subtask $4$ (42 points): $1 \leq N \leq 500$.

Translated by ChatGPT 5