APIO '16 P1 - Boat

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types
Allowed languages
C, C++, Java, Pascal

In the city of Seoul, a river called the Han River flows in the east-west direction. On the northern shore of the river there are N boating schools numbered from 1 to N as you move from the western end to the eastern end of the shore. All boats from the same school have the exact same color and thus are indistinguishable. The boats from different schools always have different colors and thus are always distinguishable. The school numbered i may choose to not send any boats to the festival. If it chooses to send boats to the festival it may send any number of boats from a_i to b_i, inclusive. (a_i \le b_i)

One key condition is that the number of boats sent by the school numbered i, if it has chosen to send any boats, should be larger than the number of boats sent by any school numbered less than i, if any such school have chosen to send boats.

Task Given a_i's and b_i's for all schools, find the number of all possible ways the schools may send boats to the festival, under the condition that at least one school chooses to send boats.

Input Specification

The first line of the input contains a single integer N — the number of schools. The i'th of the next lines contains two integers a_i and b_i. (1 \le a_i \le b_i \le 10^9)

Output Specification

The output should consist of a single line with the remainder when the number of all possible cases the schools may send boats to the festival is divided by 1\,000\,000\,007.

Sample Input

1 2
2 3

Sample Output


Explanation for Sample Output

There are 4 ways where only one school sends boats and 3 ways where both schools send boats and thus the answer is 7.


Subtask 1 (9 points):

1 \le N \le 500 and for all 1 \le i \le N, a_i = b_i.

Subtask 2 (22 points):

1 \le N \le 100 and \sum_{1 \le i \le N} (b_i - a_i) \le 10^6.

Subtask 3 (27 points):

1 \le N \le 100.

Subtask 4 (42 points):

1 \le N \le 500.


There are no comments at the moment.