Boat

In the city of Seoul, the Han River flows east to west. On the northern shore there are \(N\) boating schools, numbered \(1\) to \(N\) from west to east.

For a festival the schools send boats onto the river. Boats from the same school are identical; boats from different schools are distinguishable. School \(i\) may either send no boats, or send some number of boats \(x_i\) with \(a_i \le x_i \le b_i\).

The schools that decide to send boats must do so in strictly increasing quantity from west to east: if schools \(i < j\) both send boats then the number sent by school \(i\) must be strictly less than the number sent by school \(j\).

Count the number of distinct ways the schools can send boats to the festival (a school sending no boats is one of the possibilities), and output the count modulo \(1\,000\,000\,007\).

\(1 \le N \le 500\) and \(1 \le a_i \le b_i \le 10^9\).

• Subtask 1 (9 points): \(a_i = b_i\) for every school (each school's number of boats, if it sends any, is fixed).
• Subtask 2 (22 points): additional points, relaxing the restriction above.
• Subtask 3 (27 points): additional points.
• Subtask 4 (42 points): the general case, \(1 \le N \le 500\).

(Each subtask is scored all-or-nothing: its points are awarded only if every one of its test cases passes.)

The first line contains a single integer \(N\) — the number of schools.

Each of the next \(N\) lines contains two integers \(a_i\) and \(b_i\) \((1 \le a_i \le b_i \le 10^9)\), the inclusive range for the number of boats school \(i\) may send.

Output a single line containing the number of ways the schools can send boats, modulo \(1\,000\,000\,007\).

rip 작성

출처 APIO 2016