小Q同学最近在玩一款新出的RPG(Role-playing game)——quailty's life，其讲述的是quailty进入大学后备战ICPC Final的日常。每天他可以写一道代码题，也可以打一场比赛，还可以同时做这两件事，但是每天不做至少一件事的话他就会浑身难受然后告别ICPC生涯。
quailty定下的计划是在Final之前写够N道代码题，或者打够M场比赛，但是小Q同学发现这款游戏存在K个隐藏剧情，每个剧情有两个参数A[i],B[i](1≤ i≤ K)，表示当quailty在某一天结束时总共写了恰好A[i]道代码题并且打了恰好B[i]场比赛的话就会有挂科的危险然后回去恶补文化课，从此告别ICPC生涯。
小Q同学很好奇从quailty开始备战Final到完成计划并且不经历任何挂科危险的玩法总共有多少种，由于答案太大了，你只需要给出它对P取模的值。请注意，两种玩法是相同的，当且仅当两种玩法需要的天数相同，且每天做的事情也相同。

第一行是一个正整数T(≤ 2000)，表示测试数据组数，
对于每组测试数据，
第一行是四个由空格隔开的整数N,M,K和P，1≤ N≤1000000000,1≤ M≤10000,0≤ K≤10,1≤ P<231，
接下来K行，第i行是两个由空格隔开的整数A[i]和B[i]，1≤ A[i]≤ N,1≤ B[i]≤ M，
保证T组数据的M之和不超过100000。

对于每组测试数据，输出一个整数，表示答案对P取模的值。

5
1 1 0 100
1 1 1 100
1 1
3 3 2 100
1 1
2 2
10 10 0 1000000007
864852302 10000 10 1000000007
935671154 167
798739077 1373
779379402 2696
771351522 3845
601366924 4296
596084404 5458
475517977 6142
471467157 7402
124225405 8224
102396401 9382

3
2
12
8097453
499639715

对于第二组样例，满足条件的玩法只有两种，分别是在第一天写一道代码题，和在第一天打一场比赛。
对于第三组样例，不存在玩法使得quailty完成计划时恰好写了三道代码题又打了三场比赛。