ZOJ Problem Set - 3624
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 f from A to D and path g from B to C. f 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 f 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.
2 2 1 1 3 2 1 1
Author: ZHANG, Debing
Contest: ZOJ Monthly, July 2012