藏宝路径
【问题描述】
经过你的帮助,小Y终于得到了藏宝图。
藏宝图是一个m*n的网格。宝藏分散在(m,n)、 (m,q)两个地方。小Y、小Z分别在(0,0)、(p,0)两个位置,他们决定每个人去一个地方找宝藏。小Y去(m,n)地,小Z去(m,q)地,其中,p<m,q<n。小Y和小Z只能沿着坐标系中整数组成的网格向x轴或者y轴的正方向爬行。
小Y想知道,在两人所走的路径不重叠(两条路径没有相交的地方)的情况有多少种?
【输入格式】
输入一行,依次为m、n、p、q,都是小于100000的正整数。
【输出格式】
输出一行一个数,表示所有情况的数量 模(mod) 质数100000007的结果。
【输入输出样例】
path.in
3 2 1 1
path.out
6
【样例说明】
当小Y走(0,0)(0,2)(3,2)时,小Z有3种走法:
(1,0)(1,1)(3,1)
(1,0)(2,0)(2,1)(3,1)
(1,0)(3,0)(3,1)
类似的:
小Y还可以走(0,0) (0,1) (1,1) (1,2) (3,2),此时小Z有2种走法。
小Y还可以走(0,0) (0,1) (2,1) (2,2) (3,2),此时小Z有1种走法。
所以,共6种。
【数据规模】
对于20%的数据,m+n小于10。
对于50%的数据,m+n小于20。
对于70%的数据,m+n小于20000。
对于100%的数据,m+n小于200000。
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 5
- 已通过
- 1
- 通过率
- 20%
- 上传者