Description

The roads of Xiao B’s city form a square grid, whose southwest corner is $(0,0)$ and northeast corner is $(N,M)$.

Xiao B lives at the southwest corner, and the school is at the northeast corner. There are $T$ intersections under construction, and Xiao B cannot pass through these intersections. Xiao B prefers to take the shortest route to his destination, so each day he only moves east or north; since he also likes different routes, he asks you, under the rule of taking shortest routes, how many different routes to school he can choose. Because the answer may be large, compute the number of routes mod $P$.

Input Format

The first line contains four integers $N$, $M$, $T$, $P$. The next $T$ lines each contain two integers, denoting the coordinates of an intersection under construction.

Output Format

Output a single integer, the number of routes mod $P$.

3 4 3 1019663265
3 0
1 1
2 2

8

Hint

Translated by ChatGPT 5