NOI '19 P2 - Robot

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

There are two robots P and Q and now we are going to run some experiments on them.

There are n pillars on a row numbered from 1 to n and the height of each pillar i is a positive integer h_i. Both robots can move from one to its neighbors, which means if the robot is now at pillar i, it can only try moving to i-1 or i+1.

In each experiment, we will pick a starting pillar s and put two robots on it. Two robots will then move under certain rules:

Robot P will always move to the left, but it can't move to the pillars that are higher than pillar s. Formally, it will stop at pillar l,(l \leq s) if and only if:

  • l = 1 or h_{l-1} > h_s
  • h_j \leq h_s holds for all l \leq j \leq s

Robot Q will always move to the right, but it can only move to the pillars that are shorter than pillar s. Formally, it will stop at pillar r,(r \geq s) if and only if:

  • r = n or h_{r+1} \geq h_s
  • h_j < h_s holds for all s < j \leq r

Now for each pillar i, we can choose its height to be any integer in [A_i,B_i]. We hope that no matter which pillar we choose as the starting pillar s, the absolute difference between P and Q's moving distance (i.e. the number of pillars one robot has gone through) is not larger than 2.

Please calculate the number of plans to choose pillars' height satisfying the above condition. We consider two plans to be different if there exists a pillar k that has different height in those two plans. Since the answer may be large, please output the answer modulo 10^9+7.

Input Specification

The first line contains an integer n, indicating the number of pillars.

In the following n lines, each line contains two integers A_i, B_i.


For all test cases, 1 \leq n \leq 300, 1 \leq A_i \leq B_i \leq 10^9.

Test Casen \leOthers
1, 27A_i = B_i, B_i \le 7
3, 4B_i \le 7
5, 6, 750B_i \le 100
8, 9, 10300B_i \leq 10\,000
11, 1250A_i = 1, B_i = 10^9
13, 14, 15None
16, 17150
18, 19200

Output Specification

Output one integer on one line, the answer modulo 10^9+7.

Sample Input 1

3 3
2 2
3 4
2 2
3 3

Sample Output 1



There are no comments at the moment.