Time Limit:1000ms Memory Limit:32768KB

Description

有一辆奇怪的车子,因为它的方向盘坏了,它只能选择向前直走或者向右拐。
现在这辆车处在一个w*h大小的网格的(0,0)的地方(左上角),它需要到网格里的另一地点(x,y),
并且每一次它不能走自己之前走过的地方
问有多少种不同的方案呢?

Input

多组测试数据,每行四个数w,h,x,y (1 <= w,h <= 4000,且 0 <= x < w, 0 <= y < h)

Output

输出总的方案数,因为结果可能很巨大,为避免大整数运算,结果对10000取模输出就行了

Sample Input

1 1 0 0
3 3 1 1
4 4 1 1
4 3 2 1
10 10 5 5
20 20 10 10

Sample Output

1
4
11
5
9446
70

Hint

20 20 10 10这一组的完整结果是3903970070

Author

雨中飞燕

Source

http://yzfy.org