上学路线

时间限制:10s      空间限制:128MB

题目描述

小C所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。小C家住在西南角,学校在东北角。现在有T个路口进行施工,小C不能通过这些路口。小C喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小C又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小C只需要让你求出路径数mod P的值。


输入格式

第一行,四个整数N、M、T、P。
接下来的T行,每行两个整数,表示施工的路口的坐标。


输出格式

一行,一个整数,路径数mod P的值。


样例输入

3 4 3 1019663265
3 0
1 1
2 2

样例输出

8

提示

1<=N,M<=10^10
0<=T<=200
p=1000003或p=1019663265


题目来源

没有写明来源