问题1496--上学路线

1496: 上学路线

时间限制: 1 Sec  内存限制: 256 MB
提交: 2  解决: 1
[提交] [状态] [讨论版] [命题人:]
题目描述

小B所在的城市的道路构成了一个方形网格,它的西南角为(0,0),东北角为(N,M)。
小B家住在西南角,学校在东北角。现在有T个路口进行施工,小B不能通过这些路口。小B喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走:而小B又苒欢走不同的路径,因此他问你按照他走最短路径的规则.他可以选择的不同的上学路线有多少条。由于答案可能很大.所以小B只需要让你求出路径数mod P的值。

输入

笫一行为四个整数N、M、T、P。接下來的T行.每行两个整数,表示施工的路口的坐标。

输出

一行一个整数.表示路径数modP的值。

样例输入 Copy
3 4 3 1019663265
3 0
1 1
2 2
样例输出 Copy
8
提示
【数据范围】
测试点编号
N、M的范闱
T的范闱
P的范围
1
1<N,M<!000
0 <T< 200
1019663265
2
3
1<N,M< 100000
T= 0
P= 1000003
4
5
1 <N,M<JO9
P= 1019663265
6
7
1<N,M< 100000
0 <T< 200
P= 1000003
8
9
1 <N.M<I09
P= 1019663265
10

来源/分类