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 Case | Others | |
---|---|---|
1, 2 | , | |
3, 4 | ||
5, 6, 7 | ||
8, 9, 10 | ||
11, 12 | , | |
13, 14, 15 | None | |
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
Comments