zoj 3624(lucas定理)

C – Count Path Pair

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

Submit Status

Description

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.

Input

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

Output

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

Sample Input

Sample Output

View Code

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz