[Login|Register]
Problems

Status

Rank

Problem 1275
RG的故事
Time Limit: 1000ms
Memory Limit: 65536kb
Description
USTC的Robot Game(RG)一直都是ustcer非常喜欢的一个课外活动。现在玩RG活动的同学们遇到了一个问题:
有如下图所示的一块平面板(分成了N行M列),假设机器人总是从最左下角(0,0)出发,朝最右上角(M,N)走去。但是某些路设有障碍,机器人不能通过(图中的AB,CD,EF,HG为不能通过的路径),所以机器人必须绕过这些路而走其他的路。
现在的问题是求出机器人从起点(0,0)到终点(M,N)能走的不同的路径总数。
注意:机器人每次只能向上或向右走一步。
Input
第一行输入一个数T(T<=10),代表下面将有T组测试数据。每组测试数据包括两部分:
第一部分:四个正整数N,M,K,P(0<N,M<=10000,0<=K<=10,P为小于400的奇素数),N,M,K分别代表该平面板的行数、列数以及不能通过的路径的条数。
第二部分:K行,每行包括4个整数x1,y1,x2,y2。坐标点(x1,y1)、(x2,y2)分别代表每条路的顶点坐标,其中x1=x2或y1=y2。
数据保证所有不能通行路径都在此平面网格范围内,且没有任何两条路径完全相同,且不能通行路径的长度都为单位长度。
Output
针对每组测试数据,输出相应的路径数,如果该值大于等于P,则输出对P取模后的余数。
Sample Input
2
5 10 4 97
2 2 3 2
4 2 5 2
6 2 6 3
7 2 7 3

2 3 0 97
Sample Output
16
10
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).