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())
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
def find_inv_power(n):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod = 10**9+7
p_lis=find_power(4*10**5+100,mod)
ip_lis=find_inv_power(4*10**5+100)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)
ans=0
for i in range(h-a):
    pre=comb(i+b-1,i)
    post=comb(h+w-b-2-i,h-i-1)
    ans+=pre*post
    ans%=10**9+7
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,A,B=MI()

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

    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=cmb(N-2,H-1,mod)
    
    for i in range(min(A,B)):
        h=H-A+i+1
        w=B-i
        
        ans-=cmb(h+w-2,h-1,mod)*cmb(H+W-(h+w),H-h,mod)
        ans%=mod
        
    print(ans%mod)

main()

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

Solution (Python):


class Cmber:
    def __init__(self,gensize,mod=10**9+7):
        self.mod = mod
        self.g1=[1,1]
        self.g2 = [1, 1] 
        self.inverse = [0, 1] 
        self.getgen(gensize)
    def getgen(self,N):
        for i in range( 2, N + 1 ):
            self.g1.append( ( self.g1[-1] * i ) % self.mod )
            self.inverse.append( ( -self.inverse[self.mod % i] * (self.mod//i) ) % self.mod )
            self.g2.append( (self.g2[-1] * self.inverse[-1]) % self.mod )

    def cmb(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 cmb_very_high_n(self,n, r):
        if ( r<0 or r>n ):
            return 0
        g1=1
        r = min(r, n-r)
        for i in range(n-r+1,n+1):
            g1*=i
            g1%=self.mod
        return g1 * self.g2[r] % self.mod


def resolve():
    H,W,A,B= map(int,input().split())
    cmb= Cmber(H+W+1)
    sm =0
    for i in range(H-A):
        bef = cmb.cmb(B+i-1,i)
        r=W-B-1
        u=H-i-1
        aft = cmb.cmb(r+u,u)
        sm += (aft*bef) % 1000000007
        sm %= 1000000007

    print(sm)

if __name__ == "__main__":
    resolve()

Solution (Python):
h,w,a,b=map(int,input().split())
N=h+w
mod=10**9+7
fac=[1]*(N+2)
inv=[1]*(N+2)
t=1
for i in range(1,N+2):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+1],mod-2,mod)
for i in range(N+1,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    return fac[n]*inv[n-r]*inv[r]%mod
c=[0]
for i in range(h-a):
    c.append(comb(b+i,i))
ans=0
for i in range(h-a):
    ans+=(c[i+1]-c[i])*comb(w-b+h-i-2,w-b-1)%mod
    ans%=mod
print(ans)

Solution (Python):
h,w,a,b=map(int,input().split())
mod=10**9+7
ans=0
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 = h+w+1
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(h-a):
    p=(i)+(b-1)
    q=(h-i-1)+((w-b)-1)
    ans+=cmb(p,i,mod)*cmb(q,h-i-1,mod)
    ans%=mod
    
print(ans)

Solution (Python):
import math

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


mod = pow(10,9)+7
def divmod(num, mod=10**9+7):
    return pow(num, mod-2, mod)


def comb(a,b):
	p=fact[a-b]*fact[b]%mod
	return fact[a]*divmod(p)%mod

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


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

print(int(ans))

'''
単純なh*wのマス目だった場合

con = [[0]*w]*h
for i in range(h):
    con[i][0] = 1
for j in range(w):
    con[0][j] = 1

for k in range(1,h):
    for l in range(1,w):
        con[k][l] = con[k-1][l] + con[k][l-1]

print(con[h-1][w-1])
'''

'''
全量を計算するやり方
H*Wがデカすぎると時間というよりもメモリエラー
print('initialize')
con = [[0 for i in range(w)] for j in range(h)]



print('initialize finished')


for i in range(h-a):
    con[i][0] = 1

for j in range(w):
    
    con[0][j] = 1


for k in range(1,h-a):

    for l in range(1,b+1):
        con[k][l] = con[k-1][l] + con[k][l-1]




for m in range(1,h):


    for n in range(b,w):

        con[m][n] = con[m-1][n] + con[m][n-1]


print(con[h-1][w-1])
'''

Solution (Python):
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

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

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


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

fact = [ModInt(1, mod)]
inv = [ModInt(1, mod).inverse()] * (h + w - 1)


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


for i in range(1, h + w - 1):
    fact.append(fact[-1] * ModInt(i, mod))

inv[h+w-2] = fact[-1].inverse()
for i in range(h + w - 2, 0, -1):
    inv[i-1] = inv[i] * ModInt(i, mod)

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

print(ans)

Solution (Python):
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

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

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


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

power = [ModInt(1, mod)]
inv = [ModInt(1, mod).inverse()]


def comb(n, r):
    return power[n] * inv[r] * inv[n-r]


for i in range(1, h + w - 1):
    power.append(power[-1] * ModInt(i, mod))
    inv.append(power[-1].inverse())

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

print(ans)

Solution (Python):
mod=10**9+7
h,w,a,b=map(int,input().split())
def comb(a,b):
	p=fac[a-b]*fac[b]%mod
	return fac[a]*pow(p,mod-2,mod)%mod
fac=[1]
for i in range(h+w):
	fac.append(fac[-1]*(i+1)%mod)
ans=0
for i in range(w-b):
	p=comb(h-a-1+b+i,b+i)*comb(w-b-i-2+a,a-1)
	ans+=p%mod
	ans%=mod
print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def init_kaijo(MAX, MOD):
    kaijo = [0] * MAX
    kaijo[0] = 1
    for i in range(1, len(kaijo)):
        kaijo[i] = kaijo[i-1] * i % MOD
    return kaijo
MOD = 10**9+7
kaijo = init_kaijo(500000, MOD)

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

def nPk(n, k, MOD):
    return kaijo[n] * inv(kaijo[n-k], MOD) % MOD

def nCk(n, k, MOD):
    
    return nPk(n,k, MOD) * inv(kaijo[k], MOD)

h, w, a, b = get_nums_l()

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

print(ans % MOD)

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

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

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

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

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

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

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

Solution (Python):
def main():
    H, W, A, B = (int(i) for i in input().split())
    m = H + W + 3
    MOD = 10**9 + 7
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                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, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

    COMBinitialize(m)
    ans = 0
    for x in range(W-B):
        if x == 0:
            p = COMB(H-A-1 + B+x, B+x)
        else:
            p = COMB(H-A-1 + B+x, B+x) - COMB(H-A-1 + B+x-1, B+x-1)
        q = COMB(A+W-1-B-x, A)
        ans += p*q
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9+7
fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]
for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;
def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD

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

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

print(ans)

Solution (Python):
class Combination():
    
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        
        self.fact = [1, 1]   
        
        self.factinv = [1, 1]
        
        self.inv = [0, 1]    

        for i in range(2, N+1):
            self.fact.append((self.fact[-1] * i) % P)
            self.inv.append((-self.inv[P % i] * (P // i)) % P)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % P)
    
    
    def getComb(self, n:int, k:int):
        if (k < 0) or (n < k):
            return 0
        k = min(k, n - k)
        return self.fact[n] * self.factinv[k] * self.factinv[n-k] % self.P

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

    COMB = Combination(H+W, MOD)

    

    ans = 0
    for i in range(1,H-A+1):
        tmp = COMB.getComb((i-1)+(B-1), i-1)
        tmp *= COMB.getComb((H-i)+(W-B-1), H-i)
        ans = (ans + tmp) % MOD

    print(ans)

if __name__ == "__main__":
    main()

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 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, H+W + 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 h in range(1, H-A+1):
    ans += cmb(h-1+B-1, h-1, mod)*cmb(H-h+W-B-1, H-h, mod)
    ans %= mod

print(ans)

Solution (Python):
import sys

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def solve():
    H, W, A, B = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (H + W + 4)
    revfact = [1] * (H + W + 4)
    for i in range(1, H + W + 4): fact[i] = (i * fact[i-1]) % mod
    revfact[H + W + 3] = pow(fact[H + W + 3], mod - 2, mod)
    for i in reversed(range(1, H + W + 3)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = 0
    for j in range(B + 1, W + 1):
        up = comb(H - A + j - 2, j - 1, fact, revfact, mod)
        down = comb(A + W - j - 1, A - 1, fact, revfact, mod)
        ans += (up * down) % mod
        ans %= mod
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
import sys

def comb(n, r, fact, revfact, mod):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

def solve():
    H, W, A, B = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (H + W + 4)
    revfact = [1] * (H + W + 4)
    for i in range(1, H + W + 4): fact[i] = (i * fact[i-1]) % mod
    revfact[H + W + 3] = pow(fact[H + W + 3], mod - 2, mod)
    for i in reversed(range(1, H + W + 3)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = 0
    for j in range(B + 1, W + 1):
        up = comb(H - A + j - 2, j - 1, fact, revfact, mod)
        down = comb(A + W - j - 1, A - 1, fact, revfact, mod)
        ans += (up * down) % mod
        ans %= mod
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)

Solution (Python):
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    mod = 10 ** 9 + 7

    comb = Combination(2 * 10 ** 5 + 10, mod)

    ans = 0
    x = H - A
    y = B + 1
    while x > 0 and y <= W:
        path1 = comb(x + y - 2, x - 1)
        path2 = comb(H - x + W - y, H - x)
        ans = (ans + path1*path2) % mod
        x -= 1
        y += 1

    print(ans)

Solution (Python):
MAX = 2*10**5+100
fact = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
 
def C_init():
    fact[0] = 1
    fact[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    
    for i in range(2, MAX):
        fact[i] = fact[i-1]*i%MOD
        inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i] = finv[i-1]*inv[i]%MOD
 
def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

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

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

print(ans)

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

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

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] % mod) % mod

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

print(ans)

Solution (Python):
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    mod = 10**9+7
    comb = Combination(2*10**5+10, mod)

    ans = 0
    h1 = H - A
    w1 = B + 1
    while True:
        X = comb(h1 + w1 - 2, h1 - 1)
        h2 = H - h1
        w2 = W - w1
        Y = comb(h2 + w2, h2)
        ans += X * Y % mod
        ans %= mod

        h1 -= 1
        w1 += 1
        if h1 <= 0 or w1 > W:
            break

    print(ans)

Solution (Python):
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
rev = [1]*(mx+1)
rev[-1] = pow(fac[mx], mod-2, mod)
for i in range(mx-1, -1, -1):
	rev[i] = rev[i+1]*(i+1)%mod
const = rev[h-a-1]*rev[a-1]%mod
ans = 0
for i in range(b,w):
	ans += fac[h-a+i-1]*rev[i]*fac[a+w-2-i]*rev[w-i-1]%mod
print(ans*const%mod)

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):
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod

h,w,a,b = map(int, input().split())
mod = 10**9+7
fact = Factorial(h+w+1)
ans = 0
c,d = h-a, w-b
for i in range(b+1, w+1):
    d = w-i+1

    ans = (ans + fact.comb(i+c-2, c-1) * fact.comb(a+d-2, a-1)) % mod

print(ans)

Solution (Python):
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        self.mod = mod
        modmod = self.mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % self.mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, self.mod) % self.mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % self.mod
        return tmp * self.fac[n] % self.mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % self.mod

h,w,a,b = map(int, input().split())
mod = 10**9+7
fact = Factorial(h+w+1)
ans = 0
c,d = h-a, w-b
for i in range(b+1, w+1):
    d = w-i+1

    ans = (ans + fact.comb(i+c-2, c-1) * fact.comb(a+d-2, a-1)) % mod

print(ans)

Solution (Python):
import sys
sys.stdin.readline

MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

def main():
    H, W, A, B = map(int, input().split())
    C = Combination(H+W)
    ans = C.C(H+W-2, H-1)
    for b in range(B):
        ans -= C.C(H-A-1+b, b) * C.C(A-1+W-b-1, A-1)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
H,W,A,B = map(int,input().split())
mod = 10**9+7
x1 = [1 for i in range(H+W)]
xi = [1 for i in range(H+W)]
num = 1
def power2(a,b,p):
    if b == 0:
        return 1
    if b%2 == 0:
        d = power2(a,b//2,p)
        return (d*d)%p
    return (a*power2(a,b-1,p))%p
for i in range(1,H+W):
    num = (num*i)%mod
    x1[i] = num
for i in range(1,H+W):
    x2 = power2(x1[i],mod-2,mod)
    xi[i] = x2
def comb(a,b,p):
    return (x1[a]*xi[b]*xi[a-b])%p
ans = 0
for w in range(B,W):
    ans = (ans+ (comb(H-A+w-1,w,mod)*comb(A+W-w-2,A-1,mod))%mod)%mod
print(ans)

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

def main():
    H,W,A,B = map(int,input().split())
    MOD = 10**9+7
    fac = [0 for _ in range(H+W+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,H+W+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        num = (((fac[x+y]*invfac[x])%MOD)*invfac[y]%MOD)
        return num

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

if __name__ == "__main__":
    main()

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

F = [1]*200010
p = 1
for i in range(1, len(F)):
  F[i] = p = p*i%mod

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

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

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

fact = [1] * (h + w + 1)
invf = [1] * (h + w + 1)
invn = [1] * (h + w + 1)
for i in range(2, h + w + 1):
  fact[i] = fact[i-1] * i % mod
  invn[i] = (-invn[mod % i]) * (mod // i) % mod
  invf[i] = invf[i-1] * invn[i] % mod

count = 0
for i in range(min(h-a, w-b)):
  count += fact[h+b-a-1] * invf[h-a-i-1] * invf[b+i] * fact[w+a-b-1] * invf[a+i] * invf[w-b-i-1]
  count %= mod
print(count)

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

N = 10**6     
mod = 10**9+7 
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 path(a,b):
  h=b[0]-a[0]
  w=b[1]-a[1]
  return cmb(h+w,h,mod)
st,gl = [0,0],[H-1,W-1]
ans = path(st,gl)
for i in range(A):
  ans-=(path(st,[H-i-1,B-1])*path([H-i-1,B],gl))%mod
print(ans%mod)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

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

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    n = 2*10**5+10
    for i in range(2,n):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

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

    print(ans)


if __name__ == "__main__":
    main()