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