zoj 3624(lucas定理)

2015年10月19日 0 作者 CrazyKK
C – Count Path Pair

Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu

Submit Status


You are given four positive integers m,n,p,q(p < m and q < n). There are four points A(0,0),B(p,0),C(m,q),D(m,n). Consider the path ffrom A to D and path g from B to Cf and g are always towards and parallel to the positive direction of one axis, and they can only change their direction on integer points(whose coordinates are both integers).

You are asked to count the number(mod 100000007) of pair (f,g) that and g have no intersection.


There are multiple cases(less than 100). Each case is a line containing four integers m,n,p,q(m ≤ 100000 and n ≤ 100000).


For each case, output a single line containing the right answer.

Sample Input

Sample Output

View Code