Problem:
 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 1 2 3 1 1      Sample Output 1 2  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 2 10 7 3 4      Sample Output 2 3570  There are 12 forbidden cells.       Sample Input 3 100000 100000 99999 99999      Sample Output 3 1       Sample Input 4 100000 100000 44444 55555      Sample Output 4 738162020

Solution (Python):
class Factorial:
    def __init__(self,n,mod):
        self.f=[1]
        for i in range(1,n+1):
            self.f.append(self.f[-1]*i%mod)
        self.i=[pow(self.f[-1],mod-2,mod)]
        for i in range(1,n+1)[::-1]:
            self.i.append(self.i[-1]*i%mod)
        self.i.reverse()
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.i[i]
    def comb(self,n,k):
        return self.f[n]*self.i[n-k]%mod*self.i[k]%mod
mod=10**9+7
h,w,a,b=map(int,input().split())
f=Factorial(h+w,mod)
ans=0
for i in range(b,w):
    ans=(ans+f.comb(h-a-1+i,i)*f.comb(a-1+w-i-1,w-i-1))%mod
print(ans)

Solution (Python):
h,w,a,b=map(int,input().split())
mod=10**9+7

n=h+w+1
fc,inv=[1]*n,[1]*n
for i in range(1,n):
    fc[i]=i*fc[i-1]%mod
inv[n-1]=pow(fc[n-1],mod-2,mod)
for i in range(n-1,0,-1):
    inv[i-1]=inv[i]*i%mod
f=lambda a,b:fc[a+b]*inv[a]*inv[b]%mod

v=0
for i in range(b,w):
    v+=f(h-a-1,i)*f(a-1,w-i-1)%mod
print(v%mod)

Solution (Python):
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7


factorial = [1]
inverse = [1]
for i in range(1, H + W + 1):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))



def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % mod


ans = 0
for w in range(B, W):
    ans += nCr(H - A - 1 + w, w) * nCr(A - 1 + W - w - 1, A - 1) % mod

print(ans % mod)

Solution (Python):
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod
Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod


def combination(x, y):
    return X[x] * Y[y] * Y[x - y] % mod


for i in range(B, W):
    ans += (combination(H - A - 1 + i, i) * combination(A - 1 + W - i - 1, W - i -1))
    ans %= mod
print(ans)

Solution (Python):
H, W, A, B = [int(_) for _ in input().split()]
mod = 10**9 + 7
 
X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod
 
Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod
 
 
def comb(x, y):
    return X[x] * Y[y] * Y[x - y] % mod
 
 
ans = 0
for i in range(B, min(B + H - A, W)):
    ans += comb(H - A + B - 1, i) * comb(W + A - B - 1, W - i - 1)
    ans %= mod
print(ans)

Solution (Python):
H, W, A, B = [int(_) for _ in input().split()]
mod = 10**9 + 7

X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod

Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod


def comb(x, y):
    return X[x] * Y[y] * Y[x - y] % mod


ans = 0
for i in range(B, min(B + H - A, W)):
    ans += comb(H - A + B - 1, i) * comb(W + A - B - 1, W - i - 1)
    ans %= mod
print(ans)

Solution (Python):
h, w, a, b = map(int, input().split())
mod = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5
factorial = [1] * MAX_N

def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod



calc_factorial()
all = comb(h + w - 2, h - 1)
sub = 0
for j in range(1, b + 1):
    sub += comb(h - a - 1 + j - 1, j - 1) * comb(a - 1 + w - j, w - j)
    sub = sub % mod
if all - sub <= 0:
    print(all - sub + mod)
else:
    print(all - sub)

Solution (Python):
H, W, A, B = map(int, input().split())
h = {}
p = 10**9+7
q = p - 2
for x in range(H+W-1):
    if h.get(x-1):
        a = (x * h[x-1][0]) % p
    else:
        a = 1
    b = pow(a,q,p)
    h[x] = (a,b)

def C(n, r):
    return h[n][0] * h[r][1] * h[n-r][1]

ans = 0
for i in range(B, W):
    ans += C(i+H - A - 1, i) * C(W - 1 - i + A - 1, W - 1 - i)
    ans %= p
print(ans % p)

Solution (Python):
H, W, A, B = map(int, input().split())
h = {}
p = 10**9+7
q = p - 2
for x in range(H+W-1):
    if h.get(x-1):
        a = (x * h[x-1][0]) % p
    else:
        a = 1
    b = pow(a,q,p)
    h[x] = (a,b)

def C(n, r):
    return h[n][0] * h[r][1] * h[n-r][1]

ans = 0
for i in range(B, W):
    ans += C(i+H - A - 1, i) * C(W - 1 - i + A - 1, W - 1 - i)

print(ans % p)

Solution (Python):
mod = 10**9+7
h, w, a, b = map(int, input().split())

n = h+w-2

ans = 0
fac = [1]*(n+1)
inv = [1]*(n+1)

for i in range(1, n+1):
    fac[i] = i*fac[i-1] % mod

for i in range(1, n+1):
    inv[i] = pow(fac[i], mod-2, mod)

def func(x, y):
    m = fac[x+y]*inv[x]*inv[y]%mod
    return m

for x in range(b, w):
    ans += func(x, h-a-1)*func(w-1-x, a-1)
    ans %= mod

print(ans)

Solution (Python):
H,W,A,B = map(int,input().split())

def init_fact(n,mod):
    fact,finv,inv = [1]*n,[1]*n,[1]*n
    for i in range(2,n):
        fact[i] = (fact[i-1]*i) % mod
        inv[i]  = mod - inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1] * inv[i] % mod
    return (fact,finv,inv)

def nCr(n,r,mod,fact,finv):
    if n<r:
        return 0
    else:
        return fact[n] * (finv[r] * finv[n-r] % mod) % mod

modulo = 10**9+7
fact,finv,inv = init_fact(200000,modulo)

ans = 0
for i in range(H-A):
    ans += nCr(i+B-1,i,modulo,fact,finv) * nCr(H-i-1+W-B-1,W-B-1,modulo,fact,finv)
    ans %= modulo

print(ans)

Solution (Python):
H, W, A, B = map(int, input().split())
answer = 0
mod = 1000000007
factorial = [1]
for n in range(1, H+W):
    factorial.append(factorial[n-1]*n%mod)
def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2) ** 2 % mod
    else:
        a = power(x, y//2) ** 2
        return a * x % mod
inverseFactorial = [0] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in range(H+W-2, -1, -1):
    inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod
def combi(n, m):
    return factorial[n] * inverseFactorial[m] *inverseFactorial[n-m]%mod

for i in range(B+1, W+1):
    answer = (answer + combi(H-A-2+i, i-1)*combi(A+W-i-1,W-i)) % mod
print(answer)

Solution (Python):
H, W, A, B =  (int(i) for i in input().split())

def power(a, b):
	if b == 0:
		return 0
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007



fac_lim = 300000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007

res = conv(H+W-2, H-1)
for i in range(A):
    res -= conv(H-A+i + B-1, B-1) * conv(A-1-i + W-B-1, W-B-1)
    res = res % 1000000007

print(res)

Solution (Python):
H, W, A, B = map(int, input().split())

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * (N+1)
inv = [1] * (N+1)


for i in range(1, N+1):
    fac[i] = i * fac[i - 1] % MOD
 

for i in range(1, N+1):
    inv[i] = pow(fac[i], MOD-2, MOD)
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
    ans %= MOD
    
print(ans % MOD)

Solution (Python):
H, W, A, B = map(int, input().split())

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N


for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 

inv[N - 1] = pow(fac[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
    ans %= MOD
    
print(ans % MOD)

Solution (Python):
H, W, A, B = map(int, input().split())

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N


for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 

inv[N - 1] = pow(fac[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
    ans %= MOD
    
print(ans % MOD)

Solution (Python):
H,W,A,B=map(int,input().split())

mod=10**9+7

n=H+W
INV=[None]*(n+1)
for i in range(1,n+1):
    INV[i]=pow(i,mod-2,mod)

k=H+W-2
n=H-1
Combi1=[None]*(k+1)
Combi1[n]=1
for i in range(n+1,k+1):
    Combi1[i]=Combi1[i-1]*i*INV[i-n] %mod

k=H+B-2
n=B-1
Combi2=[None]*(k+1)
Combi2[n]=1
for i in range(n+1,k+1):
    Combi2[i]=Combi2[i-1]*i*INV[i-n] %mod

k=W-B-1+A
n=W-B-1
Combi3=[None]*(k+1)
Combi3[n]=1
for i in range(n+1,k+1):
    Combi3[i]=Combi3[i-1]*i*INV[i-n] %mod




ANS=Combi1[H+W-2]
for x in range(H-A,H):
    ANS=(ANS-Combi2[x+B-1]*Combi3[(H-x-1)+W-B-1])%mod


print(ANS)

Solution (Python):
mod=10**9+7
H,W,A,B=map(int,input().split())

Factorial=[1]*(H+W+1)
for i in range(1,H+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(H+W+1)
inverseFactorial[H+W]=power(Factorial[H+W],mod-2)
for i in range(0,H+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
ans=0
for a in range(0,H-A):
  ans=(ans+comb(B+a-1,a)*comb(W-B+H-a-2,H-a-1))%mod
print(ans)

Solution (Python):
K = 10 ** 9 + 7

def pow_K(x, n):
  if n == 0:
    return 1
  else:
    return (pow_K(x, n // 2) ** 2 * x ** (n % 2)) % K

H, W, A, B = map(int, input().split())

fact = [0 for i in range(H+W-1)]
fact[0] = 1
for i in range(H+W-2):
  fact[i + 1] = fact[i] * (i+1) % K
fact_inv = [0 for i in range(H+W-1)]
fact_inv[H+W-2] = pow_K(fact[H+W-2], K-2)
for i in range(H+W-2, 0, -1):
  fact_inv[i-1] = fact_inv[i] * i % K

r = 0
for i in range(B, W):
  r += ((fact[H-A-1+i] * fact_inv[H-A-1] %K)*fact_inv[i] % K) * ((fact[W-1-i+A-1] * fact_inv[W-1-i] %K) * fact_inv[A-1] % K) %K
  r %= K

print(r)

Solution (Python):
H, W, A, B = map(int, input().split())
M = 10 ** 5 + 5
M *= 2
fact = [0] * M
rfact = [0] * M
fact[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, M):
    fact[i] = fact[i - 1] * i % MOD

rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1) % MOD


def comb(n, k):
    return fact[n] * rfact[n - k] * rfact[k] % MOD


num = 0
for i in range(B + 1, W + 1):
    num += comb(H - (A + 1) + i - 1, i - 1) * comb(W - i + A - 1, A - 1)
    num %= MOD

print(num)

Solution (Python):
def mod_inv(inv,a,m):
    i=a
    if inv.get(a,0)!=0:
        return inv[a]
    e=m-2
    tmp=1
    while e!=1:
        if e%2==1:
            tmp*=a
            tmp%=m
        a*=a
        a%=m
        e//=2
    a*=tmp
    a%=m
    inv[i]=a
    return a

def factrial(fact,a,m):
    for i in range(1,a+1):
        fact[i]=fact[i-1]*i%mod

def comb(fact,inv,a,b,m):
    return (fact[a+b]*mod_inv(inv,fact[a],m)*mod_inv(inv,fact[b],m))%m

H,W,A,B=list(map(int,input().split()))
mod=10**9+7
fact=[1 for _ in range(H+W+1)]
inv={}
factrial(fact,H+W,mod)

ans=0
for i in range(W-B):
    ans+=comb(fact,inv,B+i,H-A-1,mod)*comb(fact,inv,W-B-1-i,A-1,mod)
    ans%=mod
print(ans)

Solution (Python):
import math
MOD = 10 ** 9 + 7
H, W, A, B = map(int, input().split())
maxf = H + W

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = i * f[i - 1] % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = invf[i] * i % MOD

comb = lambda a, b: f[a + b] * invf[a] * invf[b] % MOD

ans = 0
for x in range(B, W):
    ans += comb(x, H - A - 1) * comb(W - 1 - x, A - 1) % MOD
print(ans % MOD)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)


def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m
N = 10**9+7
R = 10**5*2
modfact = [0]*(R+1)
def modfact_memo(n,N):
    r = 1
    modfact[0] = 1
    for i in range(1,n+1):
        r = r % N * i % N
        modfact[i] = r
modfact_memo(R,N)


modinv=[0]*(R+1)
def modinv_memo(a,m):
    for i in range(a+1):
        j = modfact[i]
        (inv, q, gcd_val) = egcd(j, m)
        modinv[i] = inv % m
modinv_memo(R,N)

def modconb(n,r,N):
    p = modfact[n]
    q1 = modinv[r]
    q2 = modinv[n-r]
    return p*q1%N*q2%N

H,W,A,B = map(int,input().split())
ans = 0
for r in range(B,W):
    ans += modconb(H-A-1+r,r,N)*modconb(A-1+W-r-1,A-1,N)
    ans %= N

print(ans)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


class Combination:
    def __init__(self, n, mod):
        assert 0 < n
        self.mod = mod
        self.fact = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for i in range(1, len(self.fact)):
            self.fact[i] = (i * self.fact[i - 1]) % self.mod
            self.inv[i] = pow(self.fact[i], self.mod - 2, self.mod)

    def nCr(self, n, k):
        if n == 0 and k == 0:
            return 1
        assert 0 <= n < len(self.fact) and 0 <= k
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


def main():
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7

    comb = Combination(100000 * 2 + 10, MOD)

    ans = 0
    for i in range(B + 1, W + 1):
        h, w = H - A - 1, i - 1
        s = comb.nCr(h + w, w) % MOD

        h, w = A - 1, W - i
        t = comb.nCr(h + w, w) % MOD

        ans += (s * t) % MOD
        ans %= MOD
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
MAX = 510000
MOD = 1000000007

fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
        
def comb(n, r):
    if n < r:           return 0
    if n < 0 or r < 0:  return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

def solve():
    ans = 0
    an = H + B - A - 1
    ar = B
    bn = W + A - B - 2
    br = W - B - 1
    for i in range(W-B):
        a = comb(an, ar)
        b = comb(bn, br)
        ans += (a * b) % MOD
        an += 1; ar += 1
        bn -= 1; br -= 1
    return ans % MOD

H, W, A, B = map(int, input().split())

comb_init()
print(solve())

Solution (Python):
mod = 1000000007
H, W, A, B = map(int, raw_input().split())

factorial = [1]
for n in xrange(1, H+W):
    factorial.append(factorial[n-1]*n%mod)

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y/2)**2 % mod
    else            : return power(x, y/2)**2 * x % mod

inverseFactorial = [0] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in xrange(H+W-2, -1, -1):
    inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod

def combi(n, m):
    return factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] % mod

sum = 0
for i in xrange(B+1, W+1):
    sum = (sum + combi(H-A-1+i-1, i-1) * combi(A-1+W-i, W-i)) % mod
print sum

Solution (Python):
iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 10**9+7 

iLBoxW=iB-1
iLBoxH=iH-iA-1
iRBoxW=iW-iB-1
iRBoxH=iH-1

iMax = max(iLBoxW+iLBoxH,iRBoxW+iRBoxH)




def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY


aM = [1]*(iMax+1)
for i in range(1,iMax+1):
    aM[i]=aM[i-1]*i %iD

aInvM = [1]*(iMax+1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
for i in range(iMax,0,-1):
    aInvM[i-1]=aInvM[i]*i % iD

iRet = 0
for iL in range(0,iLBoxH+1):
    iRet += (aM[iL+iLBoxW]*aInvM[iL]*aInvM[iLBoxW]) % iD * (aM[iRBoxW+iRBoxH-iL]*aInvM[iRBoxW]*aInvM[iRBoxH-iL])%iD
    iRet %= iD
iRet %= iD
print(iRet)

Solution (Python):
iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 10**9+7 




def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY



def fFr(iX,iR=1):
    if iR == 0 or iX == 0:
        return 1
    else :
        iRet = 1
        for i in range(iR,iX+1):
            iRet *= i
        return iRet

def fnCr(iN,iR):
    if iR == 0:
        return 1
    else:
        return fFr(iN,iR+1) // fFr(iN-iR)


aM = [1]*(iH+iW-1)
for i in range(1,iH+iW-1):
    aM[i]=aM[i-1]*i %iD

aInvM = [1]*(iH+iW-1)
aInvM[iH+iW-2] = fBiPow(aM[iH+iW-2],iD-2,iD)
for i in range(iH+iW-2,0,-1):
    aInvM[i-1]=aInvM[i]*i % iD

iRet = 0
for iL in range(0,iH-iA):
    
    iRet += (aM[iL+iB-1]*aInvM[iL]*aInvM[iB-1]) % iD * (aM[iW-iB+iH-iL-2]*aInvM[iW-iB-1]*aInvM[iH-iL-1])%iD
    iRet %= iD
iRet %= iD
print(iRet)

Solution (Python):


H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)


factorial = [1] * (H+W)
factorial[0] = 1
factorial[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod

inverse = [1] * (H+W)


inverse[H+W-1] = pow(factorial[H+W-1], mod-2, mod)
for i in range(H+W-2, 0, -1):
    
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n, r):
    
    r = min(r, n-r)
    
    numerator = factorial[n]
    
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0

while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Solution (Python):


H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)


factorial = [1] * (H+W)
factorial[0] = 1
factorial[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod

inverse = [1] * (H+W)


inverse[H+W-1] = pow(factorial[H+W-1], mod-2, mod)
for i in range(H+W-2, 0, -1):
    
    inverse[i] = inverse[i+1] * (i+1) % mod


def nCr(n, r):
    
    r = min(r, n-r)
    
    numerator = factorial[n]
    
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0

while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Solution (Python):


H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)


factorial = [0] * (H+W)
factorial[0] = 1
factorial[1] = 1
inverse = [0] * (H+W)
inverse[0] = 1
inverse[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod
    
    
    inverse[i] = pow(factorial[i], mod-2, mod)
    

def nCr(n, r):
    
    r = min(r, n-r)
    
    numerator = factorial[n]
    
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0

while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Solution (Python):


H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)


factorial = [0] * (H+W)
factorial[0] = 1
factorial[1] = 1
inverse = [0] * (H+W)
inverse[0] = 1
inverse[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod
    
    
    inverse[i] = pow(factorial[i], mod-2, mod)
    

def nCr(n, r):
    
    r = min(r, n-r)
    
    numerator = factorial[n]
    
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0

while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Solution (Python):
h,w,a,b=map(int, input().split())
n=h+w-2

mod=10**9+7
fc,inv=[1]*n,[1]*n
for i in range(1,n):
  fc[i]=i*fc[i-1]%mod
inv[n-1]=pow(fc[n-1],mod-2,mod)
for i in range(n-1,0,-1):
  inv[i-1]=inv[i]*i%mod
f=lambda a,b:fc[a+b]*inv[a]*inv[b]%mod

v=0
for x in range(b,w):
  v+=f(x,h-a-1)*f(w-1-x,a-1)%mod
print(v%mod)

Solution (Python):
H, W, A, B = map(int, input().split())

mod = 10**9 + 7
N = H + W - 2


fac = [1] * N
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % mod


inv = [1] * N
inv[N - 1] = pow(fac[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % mod


def f(x, y):
    res = fac[x + y] * inv[x] * inv[y]
    return res % mod


ans = 0
for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
print(ans % mod)

Solution (Python):
H, W, A, B = map(int, input().split())

mod = 10 ** 9 + 7


fac = [1] * (H + W - 2)

inv = [1] * (H + W - 2)
for i in range(1, H + W - 2):
    fac[i] = (fac[i - 1] * i) % mod
    inv[i] = pow(fac[i], mod - 2, mod)


def f(x, y):
    res = fac[x + y] * inv[x] * inv[y]
    return res % mod


ans = 0
for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
print(ans % mod)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,A,B=inpl()
ans = 0

MAX = H+W
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

for x1 in range(B+1,W+1):
	y1 = H-A
	x2 = A
	y2 = W-x1+1
	ans += (Comb(x1+y1-2,y1-1)*Comb(x2+y2-2,y2-1))%mod
	ans %= mod

print(ans)

Solution (Python):
h, w, a, b = map(int, input().split())
m = 10**9 + 7

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, w+h+5):
    fac.append(fac[i-1] * i % m)
    inv.append(m - inv[m%i] * (m//i) % m)
    finv.append(finv[i-1] * inv[i] % m)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % m) % m


row = []
for i in range(h-a):
    row.append(nck(b+i, i))

ans = 0
for i in range(len(row)-1):
    ans += row[i] * nck(w-b-2 + h-1-i, h-1-i)
    ans %= m

ans += row[-1] * nck(w-b-1 + a, a)
ans %= m

print(ans)

Solution (Python):

def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       

def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac


def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod



MOD = 10**9+7
n = 2*10**5 + 1

H,W,A,B = map(int, input().split())


inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)


ans = 0
for h in range(H-A):
    temp = nCr(h+(B-1), h, MOD, fac, facInv) \
            * nCr((H-h-1)+(W-B-1), W-B-1, MOD, fac, facInv)
    ans = (ans + temp) % MOD
    
print(ans)

Solution (Python):
H,W,A,B = map(int,input().split())

N = H+W+10
MOD = 10**9+7

fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for i in range(W-B):
    ans += ncr(H-1-A+B+i, H-1-A) * ncr(A-1+W-1-B-i, A-1)
    ans %= MOD
print(ans)

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


@mt
def slv(H, W, A, B):
    MOD = 10**9+7
    cmb = Combination(H+W, MOD)
    ans = 0
    for i in range(W-B):
        w1 = cmb(i+(A-1), i)
        w2 = cmb((W-i-1)+(H-A-1), (H-A-1))
        ans += w1*w2
        ans %= MOD

    return ans % MOD


def main():
    H, W, A, B = read_int_n()

    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


nCr = {}


def C(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n, r) in nCr:
        return nCr[(n, r)]
    nCr[(n, r)] = C(n-1, r) + C(n-1, r-1)
    return nCr[(n, r)]


MOD = 10**9+7  
N = 10**6
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD//i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % MOD


@mt
def slv(H, W, A, B):
    MOD = 10**9+7
    ans = 0
    for i in range(W-B):
        
        w1 = cmb(i+(A-1), i)
        w2 = cmb((W-i-1)+(H-A-1), (H-A-1))
        ans += w1*w2
        ans %= MOD

    return ans % MOD


def main():
    H, W, A, B = read_int_n()

    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


nCr = {}


def C(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n, r) in nCr:
        return nCr[(n, r)]
    nCr[(n, r)] = C(n-1, r) + C(n-1, r-1)
    return nCr[(n, r)]


MOD = 10**9+7  
N = 10**6
g1 = [1, 1]  
g2 = [1, 1]  
inverse = [0, 1]  

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD//i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % MOD


@mt
def slv(H, W, A, B):
    MOD = 10**9+7
    ans = 0
    for i in range(W-B):
        
        w1 = cmb(i+(A-1), i)
        w2 = cmb((W-i-1)+(H-A-1), (H-A-1))
        ans += w1*w2
        ans %= MOD

    return ans % MOD


def main():
    H, W, A, B = read_int_n()

    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()