题目描述

小 B 所在的城市的道路构成了一个方形网格，它的西南角为 $(0,0)$，东北角为 $(N,M)$。

小 B 家住在西南角，学校在东北角。现在有 $T$ 个路口进行施工，小 B 不能通过这些路口。小 B 喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小 B 又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小 B 只需要让你求出路径数 mod $P$ 的值。

输入格式

第一行为四个整数 $N$ 、 $M$ 、 $T$ 、 $P$。

接下来的 $T$ 行，每行两个整数，表示施工的路口的坐标。

输出格式

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

3 4 3 1019663265
3 0
1 1
2 2

8

提示