推箱子
时间限制：10s 空间限制：128MB
题目描述
二维平面上有一个可以活动的箱子位于 (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 1 1 0 100 1 1 1 100 1 1 3 3 2 100 1 1 2 2
样例输出
3 2 12 【样例解释】 对于第二组测试数据，满足条件的推法只有两种，分别是一次向右推，和一次向上推。 对于第三组测试数据，满足条件的推法都无法推到 (n,m)
提示
没有写明提示
题目来源
By Tangjz