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):
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007



def main():
	h, w, a, b = LI()

	def comb(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 ** 5 * 2
	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)

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


if __name__ == '__main__':
    main()

Solution (Python):
h,w,a,b=map(int,input().split())
factorials=[]
inverses=[]
MOD=10**9+7
factorials.append(1)
curr=1
for i in range(1,h+w+1):
  curr=(curr*i)%MOD
  factorials.append(curr)
for i in range(h+w+1):
  inverses.append(pow(factorials[i],MOD-2,MOD))
ans=0
for i in range(h-a):
  ans=(ans+factorials[b-1+i]*factorials[h-2-i+w-b]*inverses[i]*inverses[b-1]*inverses[h-1-i]*inverses[w-b-1])%MOD
print(ans)

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

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


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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, 200000 + 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 k in range(1,h-a+1):
  tmp=cmb(k-1+b-1,k-1,mod)
  tmp*=cmb(h-k+w-b-1,h-k,mod)
  ans+=tmp
  ans%=mod
print(ans)

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
size = 2*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

print(ans)

Solution (Python):
def ext_euclid(a, b):
    
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euclid(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euclid(a, mod)
    return x % mod


def comb_list_1(H, W, A, B, mod, modinv_list):
    
    ret = [0 for _ in range(H - A)]
    c = 1
    for h in range(H - A):
        ret[h] = c
        c *= h + B
        c *= modinv_list[h + 1]
        c %= mod
    return ret


def comb_list_2(H, W, A, B, mod, modinv_list):
    
    ret = [0 for _ in range(H - A)]
    
    c = 1
    for a in range(1, A + 1):
        c *= (a + W - B - 1)
        c *= modinv_list[a]
        c %= mod
    
    for h in range(H - A - 1, -1, -1):
        ret[h] = c
        c *= H - h + W - B - 1
        c *= modinv_list[H - h]
        c %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    H, W, A, B = list(map(int, input().split(' ')))
    modinv_list = [None] + [mod_inv(h, MOD) for h in range(1, H + 1)]  
    combs_1 = comb_list_1(H, W, A, B, MOD, modinv_list)
    combs_2 = comb_list_2(H, W, A, B, MOD, modinv_list)
    ans = 0
    for c1, c2 in zip(combs_1, combs_2):
        ans += c1 * c2
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)


def comb(n, k):
    return (f[n] * f_inv[k] % mod) * f_inv[n-k] % mod

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

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

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

    
    N = 2*10**5
    g1 = [1, 1] 
    g2 = [1, 1] 
    inverse = [0, 1] 
    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
    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(max(a,b)):
        ans = (ans-cmb(b+h-a-1,b-1-i,mod)*cmb(a+w-b-1,a-1-i,mod)%mod)%mod
    print(ans)



    return

if __name__ == '__main__':
    main()

Solution (Python):
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=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())
ans = 0
n = H + W - B - 1
for i in range(1, H-A+1):
  ans += comb(n-i, H-i) * comb(B+i-2, B-1) % MOD
  ans %= MOD

print(ans)

Solution (Python):

import math
h,w,a,b = list(map(int, input().split()))
p = 10**9+7








def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] 
    ifac = [1, 1] 
    inverse = [0, 1] 

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

fac, ifac = make_tables(p, h+w-2)
total = 0
for i in range(b, w):
    r1 = cmb(h-a-1+i,i,p,fac, ifac)
    r3 = cmb(a-1+w-1-i, a-1,p,fac, ifac)
    
    total = total +( r1*r3)
print(total%p)

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
for i in range(B,W):
  answer+=comb_mod(H-A-1+i,i)*comb_mod(A-1+W-1-i,W-1-i)
  answer%=MOD
    
print(answer)

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
for i in range(B,W):
  answer+=comb_mod(H-A+B-1,i)*comb_mod(W+A-B-1,W-1-i)
  answer%=MOD
    
print(answer)

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
if H-A>=W-B:
  for i in range(B,W):
    answer+=comb_mod(H-A+B-1,i)*comb_mod(W+A-B-1,W-1-i)
    answer%=MOD
else:
  for j in range(H-A):
    answer+=comb_mod(H-A+B-1,B+j)*comb_mod(W+A-B-1,W-B-1-j)
    answer%=MOD
    
print(answer)

Solution (Python):
import math
p=1000000007
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,2*(10**5)+1):
    g1.append((g1[-1]*i)%p)
    inverse.append((-inverse[p%i]*(p//i))%p)
    g2.append((g2[-1]*inverse[-1])%p)
def cmb2(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
def chwp(h,w,p):
    if h==1 or w==1:return 1
    else:return cmb2(h+w-2,h-1,p)
h,w,a,b= map(int,input().split())
ans=0
for i in range(1,h-a+1):ans=(ans+chwp(i,b,p)*chwp(h-i+1,w-b,p))%p
print(ans)

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

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,h+w+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

ans = 0

for i in range(100000):
    x = h-a-i
    y = b+1+i
    
    if 0 >= x or y > w:
        break
    
    ans += nCr(h+w-x-y,h-x,mod)*nCr(x+y-2,x-1,mod)%mod
    ans %= mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W,A,B = map(int,input().split())
    MAXN = H + W + 3
    factorial = [1]
    for i in range(1,MAXN + 1):
        factorial.append(factorial[-1]*i%MOD)
    inv_factorial = [-1] * (MAXN + 1)
    inv_factorial[-1] = pow(factorial[-1],MOD - 2,MOD)
    for i in range(MAXN - 1,-1,-1):
        inv_factorial[i] = inv_factorial[i + 1]*(i + 1)%MOD
    
    fact = lambda N:factorial[N]
    nck = lambda N,K: 0 if K > N or K < 0 else factorial[N]*inv_factorial[N - K]*inv_factorial[K]%MOD
    dist = lambda sy,sx,gy,gx: nck(gy - sy + gx - sx,gy - sy)
    ans = 0
    if H - A < W - B:
        H,W = W,H
        A,B = B,A
    
    for i in range(W - B):
        x = B + i + 1
        y = H - A - i
        ans += dist(1,1,y,x)*dist(y,x,H,W)%MOD
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
mod = 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 % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

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


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

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans = (not_ans + n) % mod
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans = (ans + n) % mod
    ans %= mod
    print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,A,B=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(H+W,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for i in range(B,W):
        ans+=COM(H-A-1+i,i)*COM(A-2+W-i,A-1)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
H,W,A,B = map(int,input().split())
N=H+W
fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)
p=10**9+7

def combination(n):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%p
        inv[i] = p - inv[p%i]*(p//i)%p
        ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%p
combination(N)

b = op(H-A+B-1, B)
res = 0
for i in range(A):
    res = (res + op(W-B-2+i, i))%p
res = (res*b)%p
for i in range(H-A):
    res = (res + op(B+i, i)*op(H-i-1+W-B-2,W-B-2))%p
if H-A==1 and W-B==1:
    res = 1
elif H-A==1:
    res = op(W-B+H-2, H-1)
elif W-B==1:
    res = op(H-A+W-2, W-1)
print(res)

Solution (Python):
h,w,a,b = map(int, input().split())
import math
ans = 0
mod = 10**9+7
l =[i for i in range(1,h+w+2)]
for i in range(1,len(l)-1):
    l[i+1] = l[i+1]*l[i]%mod
l = [1]+ l
gyakugen = [pow(l[i], mod-2, mod) for i in range(1, len(l))]
gyakugen = [1] + gyakugen
for p in range(1, w-b+1):
    ans += l[(h-a-1+b+p-1)]*l[w-(b+p)+a-1]*\
    gyakugen[h-a-1]*gyakugen[b+p-1] * gyakugen[a-1]*gyakugen[w-(b+p)]
print(int(ans)%mod)

Solution (Python):
H, W, A, B = map(int, input().split())
mod = int(1e9) + 7
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod
fact = [1 for _ in range(H+W+A+B+1)]
invf = [1 for _ in range(H+W+A+B+1)]
for i in range(H+W+A+B):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[-1] = inved(fact[-1])
for i in range(H+W+A+B, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
S = 0
for i in range(H-A):
  S += (fact[i+B-1] * invf[i] * fact[H-i+W-B-2] * invf[H-1-i]) % mod
  S %= mod
S *= (invf[B-1] * invf[W-B-1]) % mod
S %= mod

print(S)

Solution (Python):

MOD = 10**9+7
MAX = 2*10**5
fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+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 comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

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

Solution (Python):

class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod


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

Solution (Python):

class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod


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

Solution (Python):


import sys






















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def make_factorial_table(size, mod):
        '''
        fact_mod[i] は i! % mod を表す。fact_mod[0] ~ facto_mod[size] まで計算可能なテーブルを返す
        >>> make_factorial_table(20, 10**9+7)
        [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063]
        '''
        fact_mod = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod

    def combination(n, r, mod, fact_table):
        '''
        フェルマーの小定理 
        a ^ p-1 ≡ 1 (mod p)
        a ^ p-2 ≡ 1/a (mod p) (逆元)
        nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
        
        >>> m = 1000000007
        >>> fact_table = make_factorial_table(100, m)
        >>> combination(10, 5, m, fact_table)
        252
        >>> combination(100, 50, m, fact_table)
        538992043
        '''
        numerator = fact_table[n]
        denominator = (fact_table[n-r] * fact_table[r]) % mod
        
        return (numerator * pow(denominator, mod-2, mod)) % mod

    h, w, a, b = mi()
    
    
    fact_table = make_factorial_table(2 * h + 2 * w, mod)
    ans = 0
    for k in range(b, w):
        
        ans = (ans + combination(h-1-a+k, h-1-a, mod, fact_table) * combination(a-1+w-1-k, a-1, mod, fact_table)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   


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


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   


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


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   


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


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

lim = 2*10**6
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

H, W, A, B = MAP()

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

print(ans)

Solution (Python):
def combmod_pre(N, p):
    '''
    sample usage:
        p = 10**9+7
        N = 10**6
        fact, finv = combmod_pre(N, p)
        combmod(n, r, p)
    '''
    fact = [1, 1]
    finv = [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)
        finv.append((finv[-1] * inv[-1]) % p)
    return (fact, finv)


def combmod(n, r, fact, finv, p):
    '''
    sample usage:
        combmod(3000, 1000, fact, finv, p)
            p is a same value of combmod_pre's argument
            fact, finv is return value of combmod_pre
    '''
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % p


p = 10**9+7
N = 10**6
fact, finv = combmod_pre(N, p)

h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    x = combmod(h - a - 1 + j, j, fact, finv, p)
    y = combmod(a + w - 2 - j, w-1 - j, fact, finv, p)
    ans += x * y
print(ans % p)

Solution (Python):
def combmod(n, r, p):
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % p


p = 10**9+7
N = 10**6
fact = [1, 1]
finv = [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)
    finv.append((finv[-1] * inv[-1]) % p)

h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    ans += combmod(h-a-1 + j, j, p) * combmod(a+w-2 - j, w-1 - j, p)
print(ans % p)

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

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

n = h+w
fac = [1]*(n+1)
fac_inv =  [0]*(n+1)

for i in range(n):
    fac[i+1] = (fac[i] * (i+1)) %MOD
fac_inv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(n,0,-1):
    fac_inv[i-1] = (fac_inv[i] * i) % MOD
    
def comb(n,k):
    if k<0 or k>n:
        return 0
    x = (fac[n] * (fac_inv[k] * fac_inv[n-k])%MOD)%MOD
    return x

ans = 0

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

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 = 2*10**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 )

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

Solution (Python):
import sys

def comb(n, r, mod=None):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    ans = 1
    for i in range(1, r+1):
        if mod:
            x *= n+1-i
            y *= i
            x %= mod
            y %= mod
        else:
            ans *= n+1-i
            ans //= i
    ans = x*pow(y, mod-2, mod)%mod if mod else ans
    return ans

def main():
    input = sys.stdin.readline
    h, w, a, b = map(int, input().split())
    mod = pow(10, 9)+7
    
    bef, aft = 1, comb(h+w-b-2, h-1, mod)
    ans = 0
    for i in range(h-a):
        ans += bef*aft
        ans %= mod
        
        bef = bef*(i+b)*pow(i+1, mod-2, mod)%mod
        aft = aft*(h-i-1)*pow(h-i+w-b-2, mod-2, mod)%mod
        
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
MOD=10**9+7
UPPERLIMIT=2*(10**5)+1
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD

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

ans=(((MODMUL[H+W-2]*MODDIV[H-1])%MOD)*MODDIV[W-1])%MOD

x=[MODMUL[H-A+B+i-1]*MODDIV[B-1]*MODDIV[H-A+i]%MOD for i in range(A)]
y=[MODMUL[W+A-B-i-1]*MODDIV[W-B]*MODDIV[A-i-1]%MOD for i in range(A)]
for i in range(A-1, 0, -1):
  x[i]-=x[i-1]

for i in range(A):
  ans-=(x[i]*y[i]%MOD)
  ans%=MOD
  
print(ans)

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

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


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

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


def comb(a, b):
    return fac[a + b] * finv[a] * finv[b]


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

print(ans)

Solution (Python):

a,b,c,d = list(map(int, input().split()))

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 + 2
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)
    
def wh(w,h):
    return cmb(w+h,w,10**9+7)

ans = wh(b-1,a-1)


for i in range(d):
    tmp = wh(i,a-c-1) * wh(c-1,b-i-1) % p
    ans += p
    ans -= tmp
    ans %= p
    
    
print(ans)

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


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def pathVar(sx, sy, gx, gy):
    x = gx - sx
    y = gy - sy
    rst = modFacts[x + y]
    rst *= invs[x] * invs[y]
    rst %= MOD
    return rst


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

modFacts, invs = prepare(H + W)

cnt = 0
while A > 0 and B > 0:
    x = H - A
    y = B - 1
    path1 = pathVar(0, 0, x, y)
    path2 = pathVar(x, y, H - 1, W - 1)
    cnt += path1 * path2
    cnt %= MOD
    A -= 1; B -= 1

ans = pathVar(0, 0, H - 1, W - 1)
print((ans - cnt) % MOD)

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools


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)