Al Bytone's Bank Robbery Escape Route

Al Bytone, the infamous thief, has planned a bank robbery. However, he is a very poor driver and turning left gives him great trouble. Therefore, at every intersection he may either continue straight or take a right turn. Moreover, once he passes through any intersection the police will appear there and remain waiting, and he is not allowed to pass through any intersection more than once. In addition, some intersections already have police stationed and must be avoided (note that there is no police at the intersections immediately near the bank or his hideout).

The streets of Byteburg form a rectangular grid: every street is either North–South or East–West, and every two non‐parallel streets intersect. The bank is located immediately south of the south‐westernmost intersection, and Al Bytone starts his escape driving north (i.e. the first intersection he reaches is (0,0)).

You are given the coordinates of the hideout, a description of the intersections that have police stationed and a positive integer parameter \(k\). Your task is to calculate the number of different escape routes from the bank to the hideout that comply with the above requirements, and then output the residue of that number modulo \(k\). The final answer should be computed in \(\mod k\) arithmetic.

Note: The input uses a coordinate system for intersections. The bank is not considered an intersection. Its location is implicitly just south of the intersection at (0,0), which is always the starting intersection.

inputFormat

The input is read from standard input and consists of:

1. A line with two space‐separated integers \(h_x\) and \(h_y\) representing the coordinates of the hideout intersection.
2. A line with a single integer \(n\), the number of intersections where police are already present.
3. Then \(n\) lines follow, each containing two space‐separated integers \(x\) and \(y\) indicating the coordinates of an intersection with police. (Note: none of these intersections will be (0,0) or the hideout.)
4. A final line containing the positive integer \(k\), the modulus.

Remember: the bank is located just south of (0,0) and the first move is always north into (0,0).

outputFormat

The output consists of a single integer which is the residue modulo \(k\) of the number of valid escape routes from the bank to the hideout.

sample

0 0
0
100

1