luogu#P4478. [BJWC2018] 上学路线
[BJWC2018] 上学路线
题目描述
小 B 所在的城市的道路构成了一个方形网格,它的西南角为 ,东北角为 。
小 B 家住在西南角,学校在东北角。现在有 个路口进行施工,小 B 不能通过这些路口。小 B 喜欢走最短的路径到达目的地,因此他每天上学时都只会向东或北行走;而小 B 又喜欢走不同的路径,因此他问你按照他走最短路径的规则,他可以选择的不同的上学路线有多少条。由于答案可能很大,所以小 B 只需要让你求出路径数 mod 的值。
输入格式
第一行为四个整数 、 、 、 。
接下来的 行,每行两个整数,表示施工的路口的坐标。
输出格式
一行一个整数,表示路径数 mod 的值。
3 4 3 1019663265
3 0
1 1
2 2
8