D - Iroha and a Grid

Contest Duration: 2016-07-23(Sat) 12:00 - 2016-07-23(Sat) 13:40 (local time) (100 minutes) Back to Home

D - Iroha and a Grid Editorial

Time Limit: 2 sec / Memory Limit: 256 MiB

配点 : $400$ 点

問題文

縦 $H$ マス、横 $W$ マスのマス目があります。いろはちゃんは、今一番左上のマス目にいます。そして、右か下に1マス移動することを繰り返し、一番右下のマス目へと移動します。ただし、下から $A$ 個以内、かつ左から $B$ 個以内のマス目へは移動することは出来ません。

移動する方法は何通りあるか求めてください。

なお、答えは非常に大きくなることがあるので、答えは $10^9+7$ で割ったあまりを出力してください。

制約

$1 ≦ H, W ≦ 100,000$
$1 ≦ A < H$
$1 ≦ B < W$

入力

入力は以下の形式で標準入力から与えられる。

 $H$   $W$   $A$   $B$

出力

移動する方法の数を $10^9+7$ で割ったあまりを出力せよ。

入力例 1Copy

Copy

2 3 1 1

出力例 1Copy

Copy

$2×3$ マスありますが、左下の $1$ マスには移動することができません。「右右下」、「右下右」という $2$ つの移動の仕方があります。

入力例 2Copy

Copy

10 7 3 4

出力例 2Copy

Copy

移動できないマスが $12$ マスあります。

入力例 3Copy

Copy

100000 100000 99999 99999

出力例 3Copy

Copy

入力例 4Copy

Copy

100000 100000 44444 55555

出力例 4Copy

Copy

738162020

Score : $400$ points

Problem Statement

We have a large square grid with $H$ rows and $W$ columns. Iroha is now standing in the top-left cell. She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.

However, she cannot enter the cells in the intersection of the bottom $A$ rows and the leftmost $B$ columns. (That is, there are $A×B$ forbidden cells.) There is no restriction on entering the other cells.

Find the number of ways she can travel to the bottom-right cell.

Since this number can be extremely large, print the number modulo $10^9+7$ .

Constraints

$1 ≦ H, W ≦ 100,000$
$1 ≦ A < H$
$1 ≦ B < W$

Input

The input is given from Standard Input in the following format:

 $H$   $W$   $A$   $B$

Output

Print the number of ways she can travel to the bottom-right cell, modulo $10^9+7$ .

Sample Input 1Copy

Copy

2 3 1 1

Sample Output 1Copy

Copy

We have a $2×3$ grid, but entering the bottom-left cell is forbidden. The number of ways to travel is two: "Right, Right, Down" and "Right, Down, Right".

Sample Input 2Copy

Copy

10 7 3 4

Sample Output 2Copy

Copy

There are $12$ forbidden cells.

Sample Input 3Copy

Copy

100000 100000 99999 99999

Sample Output 3Copy

Copy

Sample Input 4Copy

Copy

100000 100000 44444 55555

Sample Output 4Copy

Copy

738162020