Counting Shortest Paths with Obstacles

In this problem, you are given a grid of intersections where the southwest corner is \((0,0)\) and the northeast corner is \((N,M)\). Small B lives at \((0,0)\) and his school is located at \((N,M)\). There are \(T\) intersections under construction that small B cannot pass through. Since small B only takes the shortest path to school, he only moves either east (increasing the second coordinate) or north (increasing the first coordinate). He is curious about how many different shortest routes he can take, while avoiding the blocked intersections. Because the answer might be very large, you are required to output it modulo \(P\).

Formally, you are to compute the number of paths from \((0,0)\) to \((N,M)\) under the following conditions:

• You may only move to the north or east at each step.
• You cannot step on an intersection that is under construction.
• The final answer is the number of valid shortest paths modulo \(P\).

Note: The coordinates of the blocked intersections are given, and they lie within the grid boundaries.

inputFormat

The first line contains four space-separated integers \(N\), \(M\), \(T\), and \(P\):

• \(N\): the maximum first coordinate (north direction).
• \(M\): the maximum second coordinate (east direction).
• \(T\): the number of blocked intersections.
• \(P\): the modulo divisor.

Then \(T\) lines follow, each containing two space-separated integers \(x\) and \(y\) representing the coordinates of an intersection that is under construction.

outputFormat

Output a single integer: the number of shortest paths from \((0,0)\) to \((N,M)\) that avoid the blocked intersections, taken modulo \(P\).

sample

2 2 1 1000000007
1 1

2