Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3624
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
Contest: ZOJ Monthly, July 2012
Submit    Status