## NOI '19 P2 - Robot

View as PDF

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

Problem type

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

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

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

Robot will always move to the left, but it can't move to the pillars that are higher than pillar . Formally, it will stop at pillar if and only if:

• or
• holds for all

Robot will always move to the right, but it can only move to the pillars that are shorter than pillar . Formally, it will stop at pillar if and only if:

• or
• holds for all

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

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 that has different height in those two plans. Since the answer may be large, please output the answer modulo .

#### Input Specification

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

In the following lines, each line contains two integers .

#### Constraints

For all test cases, .

Test CaseOthers
1, 2
3, 4
5, 6, 7
8, 9, 10
11, 12
13, 14, 15None
16, 17
18, 19
20

#### Output Specification

Output one integer on one line, the answer modulo .

#### Sample Input 1

5
3 3
2 2
3 4
2 2
3 3

#### Sample Output 1

1