### 问题描述 小蓝所在的城市的道路构成了一个方形网格，它的西南角为 $(0,0)$，东北角为 $(N,M)$。 小蓝家住在西南角，学校在东北角。现在有 $T$ 个路口进行施工，小蓝不能通过这个路口。小蓝喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走，而小蓝又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能过大，所以小蓝只需要让你求出路径数对 $P$ 取模的值。 ### 输入格式 第一行包含四个整数 $N,M,T,P$，分别表示网格的长、宽、路口的数量以及取模的数值。 接下来 $T$ 行，每行两个整数，表示施工的路口的坐标。 ### 输出格式 输出包含一个整数，表示路径数对 $P$ 取模的值。 ### 样例输入 ```text 3 4 3 1019663265 3 0 1 1 2 2 ``` ### 样例输出 ```text 8 ``` ### 评测数据规模 对于 $20\%$ 的数据， $1\leq N,M\leq 1000$， $0\leq T\leq 200$， $P=1019663265$。 另有 $20\%$ 的数据， $1\leq N,M\leq 10^5$， $T=0$， $P=1000003$。 另有 $20\%$ 的数据， $1\leq N,M\leq 10^9$， $T=0$， $P=1019663265$。 另有 $20\%$ 的数据， $1\leq N,M\leq 10^5$， $0\leq T\leq 200$， $P=1000003$。 另有 $20\%$ 的数据， $1\leq N,M\leq 10^9$， $0\leq T\leq 200$， $P=1019663265$。 对于所有测试数据， $1\leq N,M\leq 10^9$， $0\leq T\leq 200$， $P=1000003$ 或 $P=1019663265$。