推箱子

内存限制：128 MiB 时间限制：10 Sec

二维平面上有一个可以活动的箱子位于 (0,0) ，现在可以对它施加三种操作：

向右方推，横坐标增加 1

向上方推，纵坐标增加 1

向右上方推，横纵坐标均增加 1

而平面上还有 k 个不可活动的箱子位于第一象限的一些整点上，

活动的箱子不能推到这些整点上。可能存在一些不可活动的箱子位于同一个点，可以认为它们垒在了一起。现在希

望将活动的箱子推到直线 x=n 或直线 y=m 上并立即停止活动，问有多少种推法，答案对 p 取模。两种推法视为

相同的，当且仅当它们的操作次数相等且每一次的操作相等。

第一行有一个正整数 t ，表示数据组数。

对于每组测试数据：

第一行有四个非负整数 n,m,k,p ，相邻数字间有一个空格。

接下来 k 行，每行有两个正整数 a,b ，表示一个不可活动的箱子位于 (a,b) ，相邻数字间有一个空格。

保证 1≤a≤n,1≤b≤m 。 t≤2000,tot≤10^5,1≤N≤10^4,1≤M≤10^9,0≤k≤10,1≤p<2^31

共 t 行，每行对应一组测试数据，为一个非负整数表示答案对 p 取模后的值。


			3

2

12

【样例解释】

对于第二组测试数据，满足条件的推法只有两种，分别是一次向右推，和一次向上推。

对于第三组测试数据，满足条件的推法都无法推到 (n,m)

#4587. 推箱子