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