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, max_fact, mod):
        
        
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 2 * 10 ** 6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = comb(H + W - 2, H - 1)
for x in range(H - A, H):
    ans -= comb(x + B - 1, B - 1) * comb(H - 2 - x + W - B, W - B - 1)
    ans %= mod
print(ans)

Solution (Python):
class Factorial:
    def __init__(self, max_fact, mod):
        
        
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 2 * 10 ** 6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = comb(H + W - 2, H - 1)
for x in range(H - A, H):
    ans -= comb(x + B - 1, B - 1) * comb(H - 2 - x + W - B, W - B - 1)
    ans %= mod
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % mod

H, W, A, B = getNM()

mother = cmb((H - 1) + (W - 1), (W - 1))

goban = cmb((H - A) + (B - 1), B - 1)
togoal = cmb((A - 1) + (W - B - 1), (W - B - 1))

for i in range(A):
    row = H - A + i
    col = B - 1
    row_left = A - 1 - i
    col_left = W - B - 1
    mother -= cmb(row + col, row) * cmb(row_left + col_left, row_left)
    mother %= mod
print(mother)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,a,b = map(int, input().split())


M = 10**9+7 
N = h+w+10 

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

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

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

ans = 0
for i in range(h-a-1):
    ans += cmb(b+i, i, M) * cmb(w-b-2+h-1-i, w-b-2, M)
    ans %= M
i = h-a-1
ans += cmb(b+i, i, M) * cmb(w-b-1+a, a, M)
print(ans%M)

Solution (Python):
SIZE=2*10**5; MOD=10**9+7 

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

def choose(n,r): 
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0




import sys
read = sys.stdin.read
readline = sys.stdin.readline

h,w,a,b = map(int,read().split())


ans = 0
for r in range(0,h-a):
    ans += choose(b-1+r,b-1)*choose(w-b-1+h-r-1,w-b-1)

print(ans%MOD)

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

def combs(n, r):
    return facs[n] * invs[r] * invs[n-r] % mod

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

print(ans)

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


class Combination:
    """
    Usage：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


mod = 10 ** 9 + 7
comb = Combination(h+w, mod)

ans = 0
for i in range(h-a):
    ans += comb(b+i-1, i) * comb(w-b+h-i-2, w-b-1)
    ans %= mod

print(ans)

Solution (Python):
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 1000000007
class Combination(object):
    def __init__(self, N, MOD):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, n - 1)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    H, W, A, B = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    com = Combination(H + W, MOD)
    ans = 0
    for i in range(B, W):
        tmp = com.ncr(i + H - A - 1, i)
        tmp = tmp * com.ncr(W - i - 1 + A - 1, W - i - 1) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
h,w,a,b=map(int,input().split())
mod=10**9+7
N=10**6
ans=0
def comb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % 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 )
for i in range(1,h-a+1):
  ans=(ans+comb(b+i-2,i-1,mod)*comb(h+w-b-i-1,w-b-1,mod))%mod
print(ans)

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

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-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

H, W, a, b = map(int, input().split())
r = 0
for i in range(H-a):
    r = (r + mul(cmb(b-1+i, i), cmb(W-b-1+H-i-1, W-b-1))) % mod
print(r)

Solution (Python):
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = x * i % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = x * (i + 1) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD



def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD



def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD) % MOD
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_factorials(limit: int, MOD: int) -> list:
    """Compute a mod table of factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow()."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD



def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact = get_factorials(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  
    f = lambda i: mod_comb_with_pow(x + i, i, MOD) * mod_comb_with_pow(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD



def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

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

def powmod(a, n, mod):
    p = 1
    while n > 0:
        if n % 2 == 0:
            a = a**2 % mod
            n /= 2
        else:
            p *= a
            p %= mod
            n -= 1
    return p


def invmod(a, mod):
    return powmod(a, mod-2, mod)


def combmod(n, k, mod):
    if n < k : return 0
    else:
        if n < 2*k: k = n-k
        bunsi = fac[n]
        bunbo = inv[k] * inv[n-k]
        return bunsi * bunbo % mod

fac = [1] * (H+W+1)
inv = [1] * (H+W+1)
for i in range(H+W+1):
    if i == 0:
        fac[i] = 1
        inv[i] = 1
    else:
        fac[i] = fac[i-1] * i % INF
        inv[i] = inv[i-1] * invmod(i, INF) % INF

ans = 0
for i in range(min(W, H - A + B) - B):
    h = H - A - i
    w = B + 1 + i
    ans += combmod(h+w-2, h-1, INF) * combmod(H+W-h-w, H - h, INF) % INF

print(ans%INF)

Solution (Python):
H, W, A, B = map(int, input().split())
P = 10**9+7
fa = [1]
for i in range(1, 202020):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, 202020)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

calc = lambda a, b: fa[a+b] * fainv[a] * fainv[b] % P

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

print(ans)

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

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

mod = 10**9+7 
N = (10**5)*2+5
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 )
    
    
w=[]
for i in range(W):
    w.append(cmb(H-A-1+i,i,mod))

w=w[B:]

ans=[]
for i in range(len(w)):
    ans.append(cmb(A-1+(W-B-1-i),W-B-1-i,mod)*w[i])

print(sum(ans)%mod)

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

    
    nmax = 2 * 10 ** 5 + 1  
    fac = [0] * (nmax + 1)
    finv = [0] * (nmax + 1)
    inv = [0] * (nmax + 1)
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    p = (comb(b+(h-a-1), b) * comb((w-b-1)+(a-1), a-1)) % mod
    ans = p
    for x in range(b+1, w):
        p = (((p * (x + (h-a-1)))%mod) * ((inv[x] * inv[(w-x)+(a-1)])%mod) * (w-x)) % mod
        ans = (ans + p) % mod
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def comb(n,k):
    return (ex[n]*pow(ex[k],mod-2,mod)*pow(ex[n-k],mod-2,mod))%mod

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

ex = [1]
for i in range(1,2*10**5+1):
    ex.append((ex[-1]*i)%mod)

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

print(ans)

Solution (Python):
def solve():
	h,w,a,b = map(int, input().split())
	mx = max(h,w)
	mod = 10**9+7
	fac = [1]*(h+w+1)
	for i in range(1,h+w+1):
		fac[i] = fac[i-1]*i%mod
	inv = [1]*(mx+1)
	inv[-1] = pow(fac[mx], mod-2, mod)
	for i in range(mx-1, -1, -1):
		inv[i] = inv[i+1]*(i+1)%mod
	const = inv[h-a-1]*inv[a-1]%mod
	ans = sum(fac[h-a+i-1]*inv[i]*fac[a+w-2-i]*inv[w-i-1]%mod for i in range(b,w))
	print(ans*const%mod)

if __name__=="__main__":solve()

Solution (Python):
def getlist():
	return list(map(int, input().split()))
H, W, A, B = getlist()
H -= 1
W -= 1
N = H + W + 2

const = 10 ** 9 + 7
fac = [0] * (N + 1)
inv = [0] * (N + 1)
finv = [0] * (N + 1)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

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

ans = 0
i = 0
while H - A - i > 0 and W - B - i > 0:
	ans += fac[H - A + B] * finv[B + i] * finv[H - A - i] * fac[W - B + A] * finv[A + i] * finv[W - B - i]
	ans %= const
	i += 1

if H - A - i == 0:
	ans += fac[W - B + A] * finv[A + i] * finv[W - B - i]
else:
	ans += fac[H - A + B] * finv[B + i] * finv[H - A - i]

ans %= const
print(ans)

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

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

comb = Combination(H + W + 100)

ans = 0

for b in range(B + 1, W + 1):
    ans += comb.ncr(H - A - 1 + b - 1, b - 1) * comb.ncr(A - 1 + W - b, A - 1)
    ans %= MOD

print(ans)

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

MAXN = H+W+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+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-A+W-2-i, W-1-i) * ncr(A-1+i, i)
    ans %= MOD
print(ans)

Solution (Python):
H, W, A, B = map(int, input().split())
mod = 10**9 + 7
N = 200001
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, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

    ans += (cmb(B+i-2, B-1, mod)) * cmb((W-B-1) + (H-i), W-B-1, mod)
    ans %= mod


print(ans)

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

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

mod = 10**9+7
N = max(H,W)*2
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)

L1 = []
for i in range(W-B):
    L1.append(cmb(H-A-1+B+i, H-A-1, mod))
    


answer = 0
for i in range(len(L1)):
    answer = (answer + L1[i]*cmb(A+W-B-2-i, A-1, mod)) % mod

print(answer)

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


f=[1]
for i in range(h+w):
  f.append(f[i]*(i+1)%mod)



def comb(n, r, p):
  return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p


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

print(ans%mod)

Solution (Python):
def factorials(n,m):
    
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

h,w,a,b = map(int, input().split())

f,g = factorials(h+w,10**9+7)

ans = 0

for i in range(b,min(w,h-a+b)):
    ans += f[h+b-a-1]*g[h+b-a-1-i]*g[i] * f[w+a-b-1]*g[a-b+i]*g[w-i-1]
    ans %= 10**9+7

print(ans)


"""
nCr = f[n]*g[n-r]*g[r]
nCr %= m
"""

Solution (Python):

def get_fact(lim):
    
    fact = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        fact[i] = x
    return fact

def get_inv(lim):
    
    inv = [1] * (lim + 1)
    inv[lim] = pow(fact[lim], MOD - 2, MOD)
    x = inv[lim]
    for i in range(lim - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x
    return inv

def comb(n: int, r: int) -> int:
    
    return fact[n] * inv[n - r] * inv[r]


def main():
    global MOD, fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = get_fact(H + W)
    inv = get_inv(H + W)
    ans = 0
    x, y = H - A - 1, W + A - 2
    for i in range(B, W):
        ans += comb(x + i, i) * comb(y - i, A - 1)
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def get_fact(lim):
    
    fact = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        fact[i] = x
    return fact

def get_inv(lim):
    
    inv = [1] * (lim + 1)
    inv[lim] = pow(fact[lim], MOD - 2, MOD)
    x = inv[lim]
    for i in range(lim - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x
    return inv

def comb(n: int, r: int) -> int:
    
    return fact[n] * inv[n - r] * inv[r]


def main():
    global MOD, fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = get_fact(H + W)
    inv = get_inv(H + W)
    ans = 0
    for i in range(B, W):
        ans += comb(i + H - A - 1, i) * comb(W - i - 1 + A - 1, A - 1)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def get_fact(lim):
    
    fact = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        fact[i] = x
    return fact

def get_inv(lim):
    
    inv = [1] * (lim + 1)
    inv[lim] = pow(fact[lim], MOD - 2, MOD)
    x = inv[lim]
    for i in range(lim - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x
    return inv

def comb(n: int, r: int) -> int:
    
    return fact[n] * inv[n - r] * inv[r]


def main():
    global MOD, fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = get_fact(H + W)
    inv = get_inv(H + W)
    ans = 0
    for i in range(B, W):
        ans += comb(i + H - A - 1, i) * comb(W - i - 1 + A - 1, A - 1)
    print(ans % MOD)


if __name__ == "__main__":
    main()

Solution (Python):

def comb(n: int, r: int) -> int:
    return fact[n] * inv[n - r] * inv[r]


def main():
    global fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    
    fact, x = [1] * (H + W + 1), 1
    for i in range(1, H + W + 1):
        x = (x * i) % MOD
        fact[i] = x
    
    inv = [1] * (H + W + 1)
    inv[-1] = pow(fact[-1], MOD - 2, MOD)
    x = inv[-1]
    for i in range(H + W - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x

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


if __name__ == "__main__":
    main()

Solution (Python):
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
wall = [0 for _ in range(H - A)]
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 combi(self,n,k):
        return self.f[n]*self.i[n-k]%mod*self.i[k]%mod
f = Factorial(H + W, mod)
for i in range(H - A):
  wall[i] = f.combi(B + i - 1, i) * f.combi(W + H - B - i - 2, W - B - 1) % mod
print(sum(wall) % mod)

Solution (Python):
H,W,A,B=map(int,input().split())
MOD=10**9+7
max_n=10**5*2
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD
a=0
for i in range(min(H-A,W-B)):
    a+=comb(H-A+B-1,B+i)*comb(W-B+A-1,W-B-i-1)
    a%=MOD
print(a)

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

def init(n):
    
    global factorial, inverse
    
    factorial = [1]*(n+1)
    inverse = [1]*(n+1)

    fact = 1
    for p in range(1,n+1):
        fact *= p
        fact %= mod
        factorial[p] = fact

    inv = pow(fact, mod-2, mod)
    inverse[n] = inv
    for p in range(2,n+1)[::-1]:
        inv *= p
        inv %= mod
        inverse[p-1] = inv

def comb(n,r):
    if n < r:
        return 0
    return factorial[n] * inverse[n-r] * inverse[r] % mod

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

init(10**6)

def cal(i,j):
    return comb(i+j,i)

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

ans %= mod
print(ans)