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:
- 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:
- 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 .
The first line contains an integer , indicating the number of pillars.
In the following lines, each line contains two integers .
For all test cases, .
|5, 6, 7|
|8, 9, 10|
|13, 14, 15||None|
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