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):
MODD = 10**9 + 7 

def modinv(a,m)-> int:
    b = m
    u = 1
    v = 0
    while (b):
        t = a // b
        a -= t * b
        a,b= b,a
        u -= t * v
        u,v= v,u
    u %= m
    if (u < 0):
        u += m
    return u


fac=[1]*200001
infac=[1]*200001
aaa=1
for i in range(1,200001):
    aaa=(aaa*i)%MODD
    fac[i]=aaa
    infac[i]=modinv(aaa,MODD)
    

import math as m

def perm(x,y,z) -> int:
    
    return ((fac[x]*infac[y]*infac[z])%MODD)

h,w,a,b= [int(x) for x in input().split()]
A = h-a
B = b-1
C = h-1
D = w-b-1
j=0
k=B
kl = C
jl = D
ans = 0
for i in range(A):
  ans+=perm(B+i,B,i)*perm(C+D-i,C-i,D)
print(ans%MODD)

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**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 )
ans=cmb(h+w-2,h-1,mod)
for i in range(h-a+1,h+1):
    ans-=cmb(i+b-2,i-1,mod)*cmb(h-i+w-b-1,w-b-1,mod)
    ans%=mod
print(ans)

Solution (Python):

import sys
from math import factorial

MOD = 10 ** 9 + 7

def combInit(n):
    fact = [1]
    finv = [1]
    for i in range(1, n + 1):
        fact.append(fact[i - 1] * i % MOD)
        finv.append(pow(fact[i], MOD - 2, MOD))
    return [fact, finv]

def comb(n, k, f):
    if n < k:
        return 0
    elif n < 0 or k < 0:
        return 0
    else:
        return f[0][n] * (f[1][k] * f[1][n - k] % MOD) % MOD


def perm(n, r):
    return factorial(n) // factorial(r)


def gcb(a, b):
    if b == 0:
        return a
    else:
        return gcb(b, a % b)


def lcm(a, b):
    d = gcb(a, b)
    return int(a / d * b)


def surP(x):
    return x % MOD


def main():
    
    h, w, a, b = list(map(int, input().split()))     

    
    f = combInit(h + w)
    res = 0
    for i in range(b, w):
        res += comb((h-1-a)+i, i, f) * comb((a-1)+(w-1-i), w-1-i, f)

    out = surP(res)
    
    print("{}".format(out))
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





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

Solution (Python):
P = 10**9+7
fac = [1]
ifac = [1]
ff = 1
for i in range(1,200001):
  ff *= i
  ff %= P
  fac.append(ff)
  ifac.append(pow(ff, P-2, P))
def ncr(n, r): 
  return (fac[n] * ifac[r] % P * ifac[n-r] % P);

h,w,a,b = map(int,input().split())
s = 0
nC = b-1
kC = 0
nD = w-b-1+h-1
kD = h-1
for i in range(h-a):
  C = ncr(nC, kC)
  D = ncr(nD, kD)
  s = (s + C * D) % P
  nC += 1
  kC += 1
  kD -= 1
  nD -= 1
print(s)

Solution (Python):
from math import comb
h,w,a,b = map(int,input().split())
s = 0
nC = b-1
kC = 0
nD = w-b-1+h-1
kD = h-1
p = 1000000007
fac = [1]
ff = 1
for i in range(1,200001):
  ff *= i
  ff %= p
  fac.append(ff)
def ncr(n, r, p): 
  return (fac[n] * pow(fac[r], p-2, p) % p * pow(fac[n-r], p-2, p) % p);

for i in range(h-a):
  C = ncr(nC, kC, 1000000007)
  D = ncr(nD, kD, 1000000007)
  s = (s + C * D) % 1000000007
  nC += 1
  kC += 1
  kD -= 1
  nD -= 1
print(s)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    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

comb = Combination(10**6)

def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    for i in range(1, H - A + 1):
        ans += comb(i + B - 2, i - 1) * comb(H - i + W - B - 1, H - i)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
input = stdin.readline

MAX = 510000
MOD = 10**9 + 7

def MakeTable():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 COM(n, k):
    if n < k:
        return 0
    elif n < 0 or k < 0:
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

H, W, A, B = map(int, input().split())
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

N = min(H-A, W-B)
x, y = 0, 0
result = 0

MakeTable()

for _ in range(N):
    n1 = H-A-1+B+x-y
    n2 = A+W-1-B-x+y
    result += (COM(n1, B+x) * COM(n2, A+y)) % MOD
    x += 1
    y += 1

print(result%MOD)

Solution (Python):


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
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 )
H,W,A,B=map(int,input().split())
ans=0
for i in range(H-A):
  ans+=cmb(B+i-1,B-1,mod) * cmb(H-i+W-B-2,W-B-1,mod)
print(ans%mod)

Solution (Python):
def permutation(n, k, mod):
    s = 1
    for _ in range(k):
        s *= n
        s %= mod
        n -= 1
    return s

def factorial(n, mod):
    s = 1
    for i in range(1, n + 1):
        s *= i
        s %= mod
    return s

h, w, a, b = map(int, input().split())
mod = pow(10, 9) + 7
x = h - a + b - 1
y = w - b + a - 2
p = permutation(x, h - a - 1, mod) * permutation(y, a - 1, mod) % mod
ans = p
for _ in range(w - b - 1):
    x += 1
    p = p * x * (y - (a - 1)) * pow((x - (h - a - 1)) * y, mod - 2, mod) % mod
    y -= 1
    ans += p
    ans %= mod
ans = ans * pow(factorial(a - 1, mod), mod - 2, mod) * pow(factorial(h - a - 1, mod), mod - 2, mod) % mod
print(ans)

Solution (Python):
H, W, A, B = map(int, open(0).read().split())
MOD = 10**9+7
 
factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)
 
for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

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

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 

total = 0
 

for i in range(B, W):
    total += modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD

print(total)

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

tmp = 1
for i in range(H + W):
    tmp = tmp * (i + 1) % MOD
    factorials[i+1] = tmp

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 

total = 0
 

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

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 

total = 0
 

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

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

inv_factorials = list(map(lambda n: pow(n, -1, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD)
    total %= MOD
 
print(total)

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD)
    total %= MOD
 
print(total)

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

def modperm(m, n, mod):
    p = 1
    for i in range(n):
        p = p * (m - i) % mod
    return p

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = modperm(m, n, mod)
    q = pow(modperm(n, n, mod), mod - 2, mod)
    return p * q % mod

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i

    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, MOD - 2, MOD) % MOD
    tmp = tmp * pow(d, MOD - 2, MOD) % MOD

    total = (total - tmp) % MOD

print(total)

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

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = 1
    q = 1
    for i in range(n):
        p = p * (m - i) % mod
        q = q * (i + 1) % mod
    result = p * pow(q, mod - 2, mod) % mod
    return result

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i

    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, -1, MOD) % MOD
    tmp = tmp * pow(d, -1, MOD) % MOD

    total = (total - tmp) % MOD

print(total)

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

for I in range(H-1):
  ans = C = C*(W+H-B-2-I)*pow(I+1,M-2,M)%M

for I in range(1,H-A):
  C = C*(B-1+I)*(H-I)*pow(I*(W+H-B-1-I),M-2,M)%M
  ans+=C

print(ans%M)

Solution (Python):
class Factorials:
    
    def __init__(self, n, mod):
        self.mod = mod

        
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    
    def fact(self, n):
        return self.fac[n]

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

f = Factorials(2 * (10 ** 5), mod)
if h - a < w - b:
    num = h - a
else:
    num = w - b

ans = 0
for i in range(num):
    x = h - a - i
    y = b + i + 1

    ans += f.comb(x + y - 2, x - 1) * f.comb(h + w - x - y, h - x)
    ans %= mod

print(ans)

Solution (Python):
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    if MAX_N > mod:print('MAX_N > mod !')
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:
      print('n < k !')
      return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
h,w,a,b=map(int,input().split())
c=mod_comb_k()
mod=10**9+7
ans=c.comb(h+w-2,w-1)
for i in range(b):
  ans-=(c.comb(i+h-a-1,i)*c.comb(a+w-2-i,a-1))%mod
print(ans%mod)

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

MOD = 10 ** 9 + 7
N = h + w + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
a += 1
b += 1
n = h - a + b - 1
n2 = w - b + a - 1
while a <= h and b <= w:
    ans += nCk(n, b - 1) * nCk(n2, w - b)
    ans %= MOD
    a += 1
    b += 1
print(ans)

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

n = 2 * 10 ** 5
k = 2 * 10 ** 5
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def prepare_binomial_coefficients(n, k):
    for i in range(1,n+1):
        bc_num[i] = i * bc_num[i-1] % mod
    bc_num[0] = 0
    for i in range(1,k+1):
        bc_den[i] = modinv_table[i] * bc_den[i-1] % mod
    return

def binomial_coefficients(n, k):
    if n == 0 and k == 0:
        return 1
    return bc_num[n] * bc_den[k] * bc_den[n-k] % mod

bc_num = [1]*(n+1)
bc_den = [1]*(n+1)
prepare_binomial_coefficients(n, n)

mids = [0]*(w-b)
dis_mid = h - a - 1
for i in range(w-b):
    mids[i] = binomial_coefficients(dis_mid+i+b,i+b)



mids_down = [0]*(w-b)
dis_mid = a
for i in range(w-b):
    mids_down[i] = binomial_coefficients(dis_mid+w-b-i-1,w-b-i-1)



for i in range(w-b-1):
    mids_down[i] -= mids_down[i+1]



for i in range(w-b):
    mids[i] = (mids[i] * mids_down[i]) % mod



print(sum(mids)%mod)

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

n = 2 * 10 ** 5
k = 2 * 10 ** 5
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def prepare_binomial_coefficients(n, k):
    for i in range(1,n+1):
        bc_num[i] = i * bc_num[i-1] % mod
    bc_num[0] = 0
    for i in range(1,k+1):
        bc_den[i] = modinv_table[i] * bc_den[i-1] % mod
    return

def binomial_coefficients(n, k):
    if n == 0 and k == 0:
        return 1
    return bc_num[n] * bc_den[k] * bc_den[n-k] % mod

bc_num = [1]*(n+1)
bc_den = [1]*(n+1)
prepare_binomial_coefficients(n, n)

mids = [0]*(w-b)
dis_mid = h - a - 1
for i in range(w-b):
    mids[i] = binomial_coefficients(dis_mid+i+b,i+b)



mids_down = [0]*(w-b)
dis_mid = a
for i in range(w-b):
    mids_down[i] = binomial_coefficients(dis_mid+w-b-i-1,w-b-i-1)



for i in range(w-b-1):
    mids_down[i] -= mids_down[i+1]



for i in range(w-b):
    mids[i] = (mids[i] * mids_down[i]) % mod



print(sum(mids)%mod)

Solution (Python):
mod = 10 ** 9 + 7
h, w, a, b = map(int, input().split())
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (h + w + 1)
fi = [1] * (h + w + 1)
for i in range(1, h + w + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(h - a):
    ans += comb(b + i - 1, b - 1) * comb(h + w - b - i - 2, w - b - 1)
    ans %= mod
print(ans % mod)

Solution (Python):
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
 
def mul(x, y, mod):
  x %= mod
  y %= mod
  return x * y % mod
 
def div(x, y, mod):
  x %= mod
  y %= mod
  return x * mod_pow(y, mod - 2, mod) % mod
 
@lru_cache(maxsize=None)
def mod_pow(a, p, mod):
  if p == 0:
    return 1
  if p % 2 == 0:
    root = mod_pow(a, p / 2, mod)
    return root * root % mod
  else:
    return a * mod_pow(a, p - 1, mod) % mod
 
def dnm(n, mod, factorials):
  denominators = [0] * (n + 1)
  denominators[n] = div(1, factorials, mod)
  for i in reversed(range(n)):
    denominators[i] = mul(denominators[i+1], i+1, mod)
  return denominators
 
def nmr(n, mod):
  factorials = [0] * (n + 1)
  factorials[0] = 1
  for i in range(n):
    factorials[i + 1] = (i + 1) * factorials[i] % mod
  return factorials
 
def cmb(a, b, mod, factorials, factorial_divs):
    if len(factorials) == 0:
        raise
    af = factorials[a]
    bf = factorial_divs[b]
    abf = factorial_divs[a - b]
    return mul(mul(af, bf, mod), abf, mod)
 
MOD=10**9+7
H,W,A,B=map(int,input().split())
ans = 0
 
n = nmr(H+W-2, MOD)
d = dnm(H+W-2, MOD, n[H+W-2])
 
for i in range(H-A):
  x = cmb(B-1+i, B-1, MOD, n, d)
  y = cmb(H+W-3-(B-1+i), W-B-1, MOD, n, d)
  ans += x * y % MOD
  ans %= MOD
 
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    H, W, A, B = map(int, input().split())
    H -= 1
    W -= 1
    cmb = CmbMod(H + W, mod)
    cmb.prep()
    total = cmb.cmb_mod_with_prep(H + W, H)
    for w in range(B):
        tmp = (cmb.cmb_mod_with_prep(H - A + w, w) * cmb.cmb_mod_with_prep(A - 1 + W - w, A - 1)) % mod
        total -= tmp
        total %= mod
    print(total)


if __name__ == '__main__':
    resolve()

Solution (Python):
LIMIT = 2 * 10 ** 5
fac = [0] * (LIMIT + 10)
fac[0] = 1
inv = [0] * (LIMIT + 10)
MOD = 1_000_000_007
n = 1
for i in range(1, LIMIT + 1):
    n *= i
    n %= MOD
    fac[i] = n
inv[LIMIT] = pow(fac[LIMIT], MOD - 2, MOD)
for i in range(LIMIT, -1, -1):
    inv[i - 1] = (inv[i] * i) % MOD
def C(n, r):
    return (fac[n] * inv[n-r] * inv[r]) % MOD

H, W, A, B = map(int, input().split())
ans = 0
B1 = B - 1
WB1 = W - B - 1
for i in range(H - A):
    ans += C(i + B1, B1) * C(H - i - 1 + WB1, WB1)
    ans %= MOD
print(ans)

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



def mod(num):
    return num % (10 ** 9 + 7)
    
n = H + W + 1

fac = [0] * n
rev = [0] * n

fac[0] = 1

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



rev[n-1] = pow(fac[n-1], 10**9 + 5, 10**9 + 7)

for i in range(n - 2, 0, -1):
    rev[i] = mod(rev[i + 1] * (i + 1))

rev[0] = 1

t1 = [0] * (W - B)

for i in range(W - B):
    t1[i] = mod(fac[H - A - 1 + i + B] * mod(rev[B + i] * rev[H - A - 1]))
    
res = 0

for i in range(W - B):
    r = t1[i] * mod(fac[A - 1 + W - B - 1 - i] * mod(rev[A - 1] * rev[W - B - 1 - i]))
    res = mod(res + r)
    
print(res)