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):
h,w,a,b=map(int,input().split())
inv=[0]*(2*max(h,w)+1)
fact=[0]*(2*max(h,w)+1)
inv[0]=1;fact[0]=1
mod=10**9+7
for i in range(1,2*max(h,w)+1):
    fact[i]=fact[i-1]*i%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(2*max(h,w),0,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
for yoko in range(b+1,w+1):
    re=fact[yoko-1+h-1-a]*inv[h-1-a]*inv[yoko-1]%mod
    rr=fact[w-yoko+a-1]*inv[w-yoko]*inv[a-1]%mod
    ans=(ans+re*rr%mod)%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):
U = 2*10**5
MOD = 10**9+7
 
fact = [1] * (U+1)
fact_inv = [1] * (U+1)


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


fact_inv[U] = pow(fact[U], MOD-2, MOD)
for i in range(U, 0, -1):
    fact_inv[i-1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n-k]
    x %= MOD
    return x

H, W, A, B = [int(i) for i in input().split(" ")]

ans = 0

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

Solution (Python):
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


h, w, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
facts, invs = prepare(h + w, MOD)
ans = 0
ib = invs[b - 1]
iwb = invs[w - b - 1]
for down in range(h - a):
    left_pattern = facts[b - 1 + down] * ib * invs[down] % MOD
    right_pattern = facts[h - 1 - down + w - b - 1] * invs[h - 1 - down] * iwb % MOD
    ans = (ans + left_pattern * right_pattern) % MOD
print(ans)

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

fact = [1] * (H+W+1)
fact_inv = [1] * (H+W+1)
for i in range(1, H+W+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[H+W] = pow(fact[H+W], mod-2, mod)
for i in range(1, H+W+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Solution (Python):
mod = 10 ** 9 + 7
fac_table = [1 for i in range(200001)]
inv_table = [1 for i in range(200001)]


def make_table(h, w):

    for i in range(1, h + w - 1):
        fac_table[i] = fac_table[i - 1] * i % mod
        inv_table[i] = pow(fac_table[i], mod - 2, mod)


def comb(n, r):
    return fac_table[n] * inv_table[n - r] % mod * inv_table[r] % mod


def resolve():
    H, W, A, B = map(int, input().split())
    make_table(H, W)
    print(
        sum(
            [
                comb(H - A - 1 + i, i) * comb(A - 1 + W - i - 1, A - 1) % mod
                for i in range(B, W)
            ]
        )
        % mod
    )

if __name__ == "__main__":
    resolve()

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

factorial = [1 for _ in range(U + 1)]
for i in range(1, U + 1):
    factorial[i] = (factorial[i - 1] * i) % mod

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


def comb(n, k):
    if k < 0 or k > n:
        return 0
    x = factorial[n]
    x *= inverse[k]
    x %= mod
    x *= inverse[n - k]
    x %= mod
    return x
  
  
ans = 0
for i in range(H - A):
    x = comb(B - 1 + i, i)
    a = H - 1 - i
    b = W - 1 - B
    x *= comb(a + b, a)
    x %= mod
    ans += x
ans %= mod
print(ans)

Solution (Python):
import math
import time

DIV_VALUE = 10**9 + 7

def calcModOfPow(a, n, p):
    btm = a
    ans = 1
    while n != 0:
        
        if n & 1:
            ans = (ans * btm) % p
            
        n = n>>1
        btm = (btm**2) % p
        

    return ans

def calcModOfInv(a, p):
    b = p
    x = 1
    y = 0
    while b:
        div = a // b
        a -= div * b
        [a, b] = [b, a]
        x -= div * y
        [x, y] = [y, x]
    
    x %= p
    if x < 0:
        x += p

    return x

class FirstHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.sup = 0
        self.numOfCases = 1

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                (self.B + self.k - 1)
            ) * (
                calcModOfInv(self.k, DIV_VALUE)
            ) % DIV_VALUE
        self.k += 1
        
        
        
        return self.numOfCases
        

class SecondHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.numOfCases = 1
        totalval = self.H + self.W - self.B - 2
        loopval = self.H - 1 if self.H < self.W - self.B else self.W - self.B - 1
        for top in range(totalval, totalval - loopval, -1):
            self.numOfCases *= top
            self.numOfCases %= DIV_VALUE
        for bottom in range(loopval, 0, -1):
            self.numOfCases *= calcModOfInv(bottom, DIV_VALUE)
            self.numOfCases %= DIV_VALUE

        
        
        
        
        
        
        

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                self.H - self.k
            ) * (
                calcModOfInv(
                    self.H + self.W - self.B - self.k - 1,
                    DIV_VALUE
                )
            ) % DIV_VALUE
        self.k += 1
        
        
        return self.numOfCases
        

if __name__ == '__main__':
    [H, W, A, B] = [int(ipt) for ipt in input().split()]
    
    start = time.time()
    fstHlf = FirstHalf(H, W, A, B)
    sndHlf = SecondHalf(H, W, A, B)
    totalCases = 0

    mid = time.time()
    
    for _ in range(H - A):
        totalCases += (
            fstHlf.getNumOfCases() * sndHlf.getNumOfCases()
        )
        totalCases %= DIV_VALUE

    end = time.time()
    
    print(totalCases)

Solution (Python):
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    H, W, A, B = map(int, input().split())
    mod = 10**9 + 7
    c = cmbs(mod)
    r = c.cmb(H+W-2, H-1)
    for i in range(1, B+1):
        r -= c.cmb(H-A+i-2, i-1) * c.cmb(A-1+W-i, A-1)
    return r % mod
print(main())

Solution (Python):
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    H, W, A, B = map(int, input().split())
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    r = 0
    a = H - A - 1
    for i in range(B, W):
        r = (r + nCr(a + i, i) * nCr(A - 1 + W - i - 1, W - i - 1)) % mod
    return r


print(main())

Solution (Python):
class CombinationFermat:

    def __init__(self):
        """O(MAX)で前計算しておく→以降comb(a,b)はO(1)で取得可能
        """
        MOD = 10**9 + 7
        MAX = 2*10**5

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

    def comb(self, n: int, r: int) -> int:
        MOD = 10**9 + 7
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return self.fac[n] * (self.finv[r] * self.finv[n-r] % MOD) % MOD


H, W, A, B = map(int, input().split())
c = CombinationFermat()
ans = 0
MOD = 10**9 + 7

for i in range(H-A):
    x = c.comb(B-1+i, i)
    a = H-1-i
    b = W-1-B
    x *= c.comb(a+b, a)
    x %= MOD
    ans += x
ans %= MOD
print(ans)

Solution (Python):
MOD = 10**9 + 7
MAX = 2*10**5
fac = [0]*MAX  
finv = [0]*MAX  
inv = [0]*MAX  


def comb_init():
    global fac, finv, inv
    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: int, r: int) -> int:
    global fac, finv
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD


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

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

Solution (Python):
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


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

    calc = Calc(max_value=H + W, mod=MOD)

    ans = 0
    for x in range(B, W):
        v = calc.combination(n=(H - A - 1) + x, r=x)
        u = calc.combination(n=(A - 1) + (W - 1 - x), r=A - 1)
        
        ans = (ans + v * u) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


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

N = 2 * 10 ** 5 + 1000  
mod = pow(10, 9) + 7
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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

ans = 0
h, w, a, b = map(int,input().split())
for i in range(h - a):
    
    ans += (cmb(b - 1 + i, i) * cmb(w - b -  1 + h - i - 1, w - b - 1)) % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

Solution (Python):
def main():
    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)

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

    ans = cmb((H+W-2), min(H, W)-1, mod)

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


main()

Solution (Python):
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]


class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    h,w,a,b=MI()
    cc=[]
    for i in range(h-a):
        cc.append(nCr(b+i,i))
    
    ans=mint(0)
    pc=0
    for i,c in enumerate(cc):
        ans+=(c-pc)*nCr(h-1-i+w-1-b,w-1-b)
        pc=c
    print(ans)

main()

Solution (Python):
def cmb1(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
 
h,w,a,b=map(int,input().split())
 

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

Solution (Python):
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 nhr(self, n, r):  
        return self.ncr(n + r - 1, n - 1)

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

H, W, A, B = map(int, input().split())
comb = Combination(H + W + 100)
MOD = 10**9 + 7

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False


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

N = 2 * 10 ** 5 + 100  
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

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


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

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    f = [1]
    N = 1000000
    for i in range(1,N+1):
        f.append(f[-1]*i%mod)
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    h,w,a,b = LI()
    ans = 0
    y = h-a
    x = b+1
    while x <= w and y:
        ans += comb(x+y-2,x-1)*comb(h-y+w-x,w-x)%mod
        y -= 1
        x += 1
    print(ans%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
memo=[0]*(10**6+1)
memo[0]=memo[1]=1
mod=10**9+7
for i in range(2,10**6+1):
  memo[i]=(memo[i-1]*i)%mod
def comb(n,k,p):
  return (memo[n]*pow(memo[k],p-2,p)*pow(memo[n-k],p-2,p))%mod
h,w,a,b=map(int,input().split())
ans=0
for i in range(h-a):
  ans+=(comb(b+i-1,i,mod)*comb(h-i-1+w-b-1,w-b-1,mod))%mod
  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):




def gcd(b, m):
  if b == 0:
    return m
  return gcd(m%b, b)

def modInverse(b,m): 
    g = gcd(b, m) 
    if (g != 1): 
        
        return -1
    else:  
        
        
        return pow(b, m - 2, m) 
  
  

def modDivide(a,b,m): 
    a = a % m 
    inv = modInverse(b,m) 
    if(inv == -1): 
        print("Division not defined") 
    else: 
        return (inv*a) % m

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

DP = []
j = 1
for i in range(1,200002):
    j *= i
    j %= MOD
    DP.append(j)


def factorial(i):
    if (i == 0):
        return 1
    global DP
    
    
    
    return DP[i-1]

def move2(H, W, A, B):
    numPaths = 0
    h = H-A
    w = W-(W-B)+1
    a = A+1
    pttp = 0
    for b in range(w, W+1):
        
        ttp = (factorial(h+b-2)*modInverse((factorial(h-1)*factorial(b-1))% MOD, MOD)) % MOD
        tpttp = ttp
        ttp -= pttp
        pttp = tpttp
        btp = (factorial(a+(W-b+1)-2)*modInverse((factorial(a-1)*factorial(W-b))% MOD, MOD)) % MOD
        
        numPaths += ttp*btp
    return numPaths

ways = move2(H, W, A, B)
print(ways % (10**9 + 7))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

fac = [-1] * (2 * 10**6+1)
inv = [-1] * (2 * 10**6+1)
finv = [-1] * (2 * 10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(2 * 10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()

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

def modpow(base, pow, mod):
  res = 1
  while pow > 0:
    if pow & 1:
      res = res * base % mod
    base = base**2 % mod
    pow >>= 1
  return res

def modmul(a, b, mod):
  return a*b % mod

def solve(h,w,a,b):
  fact = [0]*(h+w+1)
  fact[0] = 1
  fact_inv = [0]*(h+w+1)
  fact_inv[0] = 1
  for i in range(1, h+w):
    fact[i] = fact[i-1]*i % MOD
    fact_inv[i] = modpow(fact[i], MOD-2, MOD)

  ans = 0
  for col_idx in range(b, w):
    before_checkpoint = modmul(modmul(fact[h-a-1+col_idx], fact_inv[h-a-1], MOD), fact_inv[col_idx], MOD)
    from_checkpoint = modmul(modmul(fact[(a-1) + (w-col_idx-1)], fact_inv[w-col_idx-1], MOD), fact_inv[a-1], MOD)
    ans = (ans + modmul(before_checkpoint, from_checkpoint, MOD)) % MOD

  return ans

if __name__ == "__main__":
  h,w,a,b = map(int, input().split())
  print(solve(h,w,a,b))

Solution (Python):
h, w, a, b = [int(i) for i in input().split()]

mod = 10 ** 9 + 7
kkai = [1]
for i in range(1, 210000):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


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

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


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(1000000)
MOD = 10**9+7
ans = 0
for i in range(B,W):
    ans += comb(H-A-1+i,i)*comb(A-1+W-1-i,A-1)
    ans %= MOD
    
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  


class Combination(object):

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

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        fac = self.fac
        finv = self.finv
        mod = self.MOD
        return fac[n] * (finv[k]*finv[n-k] % mod) % mod


def solve(H: int, W: int, A: int, B: int):

    cmb = Combination(H+W+1, MOD)

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    A = int(next(tokens))  
    B = int(next(tokens))  
    solve(H, W, A, B)


if __name__ == '__main__':
    main()

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

MOD = 1000000007

fac = [1, 1]
inverse = [0, 1]
ifac = [1, 1]
  
for i in range(2, H+W):
  fac.append((fac[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i))  % MOD)
  ifac.append((ifac[-1] * inverse[i]) % MOD)

def f(n):
  return fac[B+n+H-A-1] * fac[W-B-1-n+A-1] * ifac[B+n] * ifac[H-A-1] * ifac[W-B-1-n] * ifac[A-1]

def sigma(func, frm, to):
  result = 0
  for i in range(frm, to+1):
    result += func(i)
  return result
 
print(sigma(f, 0, W-B-1)%MOD)

Solution (Python):
H,W,A,B=map(int,input().split())
MAX_NUM = 2*10**5 + 1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
while 1:
    a=(a+c(H-A-1+B,B)*c(A+W-B-1,A))%pr
    A+=1
    B+=1
    if A==H or B==W:
        break
print(a)

Solution (Python):
from operator  import mul
from functools import reduce

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

p = 10 ** 9 + 7
N = 10 ** 6
fact    = [1, 1]  
factinv = [1, 1]  
inv     = [0, 1]

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






"""
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0])
W = int(in1[1])
A = int(in1[2])
B = int(in1[3])

allCNT = 0
for idx1 in range(W - B):
    beforeCNT = cmb(H - A + B - 1 + idx1, H - A - 1, p)
    afterCNT  = cmb(W + A - B - 2 - idx1, A - 1, p)
    allCNT    = (allCNT + (beforeCNT * afterCNT) % p) % p

print(allCNT)

Solution (Python):
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 2 * 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

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

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

MOD = 1000000007


def modPow(a, x, p):
    res = 1
    while (x > 0):
        if (x % 2 != 0):
            res = (res * a) % p
        a = (a * a) % p
        x /= 2
    return res


fact = [None] * 220000

for i in range(1, 220000):
    fact[0] = 1
    fact[i] = i * fact[i - 1] % MOD
    


def ncr(n, r):
    den = fact[n - r] * fact[r] % MOD
    return fact[n] * pow(den, MOD - 2, MOD) % MOD


def number_of_paths(h, w):
    n = h + w - 2
    r = h - 1
    return ncr(n, r)


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

print(int(ans % MOD))