3782 - 上学路线

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

Input

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

Output

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

Examples

Input

3 4 3 1019663265
3 0
1 1
2 2

Output

8

Hint

1<=N,M<=10^10

0<=T<=200

p=1000003或p=1019663265

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题