Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
118 - ZOJ Monthly, July 2012 - C
Count Path Pair

Time Limit: 3 Seconds      Memory Limit: 65536 KB

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.

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

2 2 1 1
3 2 1 1

Sample Output

3
6

Author: ZHANG, Debing
Submit    Status