Fax McClad, Croneria's most heroic bounty hunter has learned that Space Pirates have captured his friend Jody and locked her up in a power plant! Fax was able to free her, but the Space Pirates activated the power plant's self-destruct mechanism!
Hopping on his Kyuwing with Jody, Fax begins to fly through a long escape tunnel. From a top-down view, the tunnel can be represented as a 2-D grid which is blocks tall by blocks wide. Coordinates range from to . Fax initially begins at , and needs to fly to for any . In order to go as fast as possible due to the exploding plant behind him, Fax will only fly , , or .
However, the explosions have activated blast pillars. Fax obviously cannot fly through a pillar. Suppose that Fax is currently in . If and contain pillars, then Fax can move to if it does not contain a pillar. Similarly, if and contain pillars, then Fax can move to if it does not contain a pillar.
In summary,
- Fax will not fly through a pillar.
- Fax has the choice to fly , , or .
- If Fax is at and there are pillars at and , Fax has the choice to fly .
- If Fax is at and there are pillars at and , Fax has the choice to fly .
In addition, Fax is never allowed to move to the same location as he previously was. There are at most unique positions across all the pillars.
Please find out how many ways there are for Fax to get to the end before the power plant blows up!
Constraints
For all subtasks:
If a pillar is at , then and .
Subtask | Constraint | Score |
---|---|---|
1 | 10 | |
2 | 30 | |
3 | No additional restrictions | 60 |
Input Specification
The first line will contain the integers .
This will be followed by pairs of integers, indicating the positions for each of the pillars.
Output Specification
Print a single integer, the number of ways for Fax to go to the end modulo .
Sample Input 1
2 2 5 0
1 1
4 0
Sample Output 1
8
Sample Explanation 1
Sample Input 2
2 2 3 1
1 0
2 1
Sample Output 2
2
Sample Explanation 2
Sample Input 3
4 5 3 0
2 0
2 1
2 2
2 3
Sample Output 3
4
Comments