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

if __name__=="__main__":solve()

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

if __name__=="__main__":solve()

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(" "))
div = 10 ** 9 + 7
size = h + w - 1

fact = [0] * size
inverse = [0] * size
inv_calced = [0] * size
fact[:2] = [1, 1]
inverse[:2] = [1, 1]
inv_calced[:2] = [0, 1]

for i in range(2, size):
  fact[i] = fact[i - 1] * i % div
  inv_calced[i] = -inv_calced[div % i] * (div // i) % div
  inverse[i] = inverse[i - 1] * inv_calced[i] % div
  
result = 0
for x in range(b, w):
  y = h - a - 1
  temp_1 = (fact[x+y] * inverse[x] % div) * inverse[y] % div
  temp_2 = (fact[h+w-x-y-3] * inverse[w-x-1] % div) * inverse[h-y-2] % div
  result += ((temp_1 % div) * (temp_2 % div)) % div

print(result % div)

Solution (Python):
from math import factorial

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

fact = [1]


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


inv_fact = [pow(fact[-1], MOD-2, MOD)] 
for i in range(h+w-2, 0, -1): 
    inv_fact.append(inv_fact[-1] * i % MOD)
inv = list(reversed(inv_fact)) 


def comb(x, y):
    return (fact[x] * inv[y] * inv[x-y])

ans = 0
for x in range(b, w):
    ans += ((comb((h-a-1 + x), x)) * (comb((a-1 + w-x-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
 
h,w,a,b=map(int,input().split())
m=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,h+w):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

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

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

mod = 10**9+7
def nCr(fact, inv, n, r):
    return fact[n] * inv[r] * inv[n-r] % mod

def main():
    H,W,A,B = map(int,input().split())
    fact = [1]
    for i in range(1, H+W+1):
        fact.append(fact[i-1] * i % mod)
    
    inv = [0] * (H+W+1)
    inv[H+W] = pow(fact[H+W], mod-2, mod) 
    for i in range(H+W, 0, -1):
        inv[i-1] = inv[i] * i % mod

    ans = 0
    for i in range(W-B):
        n0 = H-A-1+B+i
        r0 = H-A-1
        n1 = A-1+W-B-1-i
        r1 = A-1
        ans += nCr(fact, inv, n0, r0) * nCr(fact, inv, n1, r1) % mod
    print(ans%mod)

if __name__ == '__main__':
    main()

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

MOD = 10 ** 9 + 7


def pow_mod(x, p):
    res = 1
    while p:
        if p % 2:
            res = res * x % MOD
        x = x * x % MOD
        p //= 2
    return res


F = [1]
invF = []


def comb_mod(n, r):
    return F[n] * invF[r] * invF[n - r] % MOD


for i in range(1, H + W - 1):
    F.append(F[-1] * i % MOD)

invF.append(pow_mod(F[-1], (MOD - 2)))
for f in range(len(F) - 1):
    invF.append(invF[-1] * (len(F) - len(invF)) % MOD)
invF = invF[::-1]

res = 0
for i in range(B + 1, W + 1):
    p = H - A - 1
    q = i - 1

    res = (
                  res
                  + comb_mod(H - A - 1 + i - 1, H - A - 1)
                  * comb_mod(A - 1 + W - i, W - i)
          ) % MOD

print(res)

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

MOD = 10**9 + 7
MAX = h+w + 5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

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

def path(x, y):
    return comb(x+y-2, x-1)

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

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

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


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


mod = 10**9+7  
N = 10**5*2
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+1):
    ans += cmb(H-A-1+i, i, mod)*cmb(W+A-2-i, W-1-i, mod)
    ans %= mod
    
print(ans)

Solution (Python):
H, W, A, B = [int(_) for _ in input().split()]
p = 10 ** 9 + 7




def power(n, x, p):
    return pow(n,x,p)
    
    
    
    
    
    
    
    


def solve():
    kaijo = [0] * (H + W + 1)
    kaijo[0] = kaijo[1] = 1
    for i in range(2, H + W + 1):
        kaijo[i] = (i * kaijo[i - 1]) % p
    gyaku = [0] * (H + W + 1)
    gyaku[0] = gyaku[1] = 1
    for i in range(2, H + W + 1):
        gyaku[i] = power(kaijo[i], p - 2, p)

    
    

    def conb(_x, _y):
        return (kaijo[_x] * gyaku[_y] * gyaku[_x - _y]) % p

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


if __name__ == '__main__':
    solve()

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

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

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(n+1)
f_mod_inverse=[1]*(n+1)
for i in range(1,n+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD

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

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

mod = 10**9 + 7

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

def comb(A,B,mod):
    return f[A] * pow(f[B],mod-2,mod) * pow(f[A-B],mod-2,mod) % mod

res = 0

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

print(res%mod)

Solution (Python):
H, W, A, B = map(int, input().split())
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 = maximum = max(H - A + W - 2, W + A - B - 2)
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

for i in range(W - B):
    
    P = 10 ** 9 + 7
    prev = cmb(H - A + B - 1 + i, H - A - 1, P) % P
    latter = cmb(A - 1 + W - B - 1 - i, A - 1, P) % P
    ans += (prev * latter) % P
    ans = ans % P
print(ans)

Solution (Python):
def main():

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

    v = 1
    fs = [v]
    for i in range(1, H+W-1):
        v = (v * i) % mod
        fs.append(v)

    v = invfactorial(H+W-2, mod)
    invfs = [v]
    for i in range(H+W-2, 0, -1):
        v = (v * i) % mod
        invfs.append(v)
    invfs = invfs[::-1]

    tot = (fs[H+W-2] * invfs[H-1] * invfs[W-1] ) % mod
    subtract = 0
    for b in range(B):
        v1 = (fs[H-1-A+b]*invfs[b]*invfs[H-1-A]) % mod
        v2 = (fs[A-1+W-1-b] * invfs[A-1] * invfs[W-1-b]) % mod
        subtract += v1 * v2
        subtract %= mod
    
    return (tot - subtract) % mod


def powquick(x, y, mod):
    if y == 0: return 1
    elif y == 1: return x % mod
    elif y % 2 == 0: return pow(powquick(x, y // 2, mod) , 2) % mod
    elif y % 2 == 1: return (x * pow(powquick(x, y // 2, mod), 2)) % mod

def invfactorial(x, mod):
    v = 1
    for i in range(1, x+1):
        v = (v * i) % mod
    return powquick(v, mod-2, mod)



if __name__ == '__main__':
    print(main())

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

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

    MOD = int(1e9) + 7

    kai = [1] * (max(H-A+W, A+W-B) + 1)
    for i in range(1, len(kai)):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD
    
    up = [0] * (W-B)
    down = [0] * (W-B)

    t1 = H-A-1
    for i in range(W-B):
        t2 = B + 1 + i-1
        
        up[i] = kai[t1 + t2] * pow(kai[t1], MOD-2, MOD) * pow(kai[t2], MOD-2, MOD)
        up[i] %= MOD
    t1 = A-1
    for i in range(W-B):
        t2 = W-B-i-1
        
        down[i] = kai[t1 + t2] * pow(kai[t1], MOD-2, MOD) * pow(kai[t2], MOD-2, MOD)
        down[i] %= MOD
    
    ans = 0
    for i in range(W-B):
        ans += (up[i] * down[i])
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

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

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

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

mod = int(10**9+7) 
NN = 10**6 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

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

MOD = 10**9 + 7

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

def div(a, b):
    return mul(a, power(b, MOD-2))


fac = [1] * N
for i in range(1, N): 
    fac[i] = fac[i-1] * i % MOD
    
invfac = [0] * (N)
invfac[H+W-1] = power(fac[H+W-1], MOD-2)
for i in range(H+W-2, -1, -1):
    invfac[i] = invfac[i+1] * (i+1) % MOD
    
def nCr(n, r):
    return fac[n] * invfac[r] * invfac[n-r] % MOD



ans = 0
f = {}
for i in range(H-A):
    h1 = i
    w1 = B-1
    if (h1, w1) in f:
        zenhan = f[(h1, w1)]
    else:
        zenhan = nCr(h1+w1,h1)
        f[(h1, w1)] = zenhan
    
    h2 = (H-1) - i
    w2 = (W-1) - B
    if (h2, w2) in f:
        kouhan = f[(h2, w2)]
    else:
        kouhan = nCr(h2+w2,h2)
        f[(h2, w2)] = kouhan

    ans += zenhan * kouhan

print(ans % MOD)

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


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

lru_cache(maxsize=None)
def cmb(c, r):
    return fc[c + r] * ic[c] * ic[r] % mod
 
fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % mod
ic = [pow(x, mod-2, mod) for x in fc]
 
if H-A <= W-B:
    for i in range(0,H-A):
        ans += cmb(i, B-1) * cmb(H - 1 - i,W - 1 -B ) % mod
else:
    for i in range(B, W):
        ans += cmb(i, H - 1 - A) * cmb(W - 1 - i, A - 1) % mod
  
print(ans%(mod))

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

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

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

MOD = 10 ** 9 + 7


def get_fact_list(n: int) -> list:
    result_list = [1]
    tmp = 1
    for i in range(n):
        tmp = (tmp * (i + 1)) % MOD
        result_list.append(tmp)

    return result_list


def get_inv_list(n: int, fact_lit: list) -> list:
    result_list = [1]

    for i in range(n):
        result_list.append(pow(fact_lit[i + 1], MOD - 2, MOD))

    return result_list


def comb(n: int, m: int, fact_list: list, inv_list: list) -> int:
    return (fact_list[n] * inv_list[m] * inv_list[n - m]) % MOD


h = H - A
w = W - B
ways = 0
fact = get_fact_list(H + W)
inv = get_inv_list(H + W, fact)

while h > 0 and w > 0:
    h -= 1
    w -= 1
    ways += (comb(H - A + B - 1, h, fact, inv) * comb(W + A - B - 1, w, fact, inv)) % MOD

print(ways % MOD)

Solution (Python):

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


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


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


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


if __name__ == "__main__":
    main()

Solution (Python):

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


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

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


if __name__ == "__main__":
    main()

Solution (Python):
H,W,A,B = map(int,input().split())
MOD = (10**9)+7
D = [0,2, 9, 11, 14, 15, 17, 19, 20, 23, 24, 25, 27, 28, 29]

def inv(a):
    ans = 1
    hoge = a
    for count in range(31):
        if (count) in D:
            ans *= hoge
            ans %= MOD
        hoge *= hoge
        hoge %= MOD
    return ans

g = [1]*(H+W)
for i in range(1,H+W):
    g[i] = (g[i-1]*i%MOD)
ans = 0
for i in range(H-A):
    L = g[B-1+i]*inv(g[B-1])*inv(g[i])
    R = g[(W-B-1)+(H-1-i)]*inv(g[(W-B-1)])*inv(g[H-1-i])
    ans += L*R%MOD
print(ans%MOD)

Solution (Python):
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
h,w,a,b=map(int,input().split())
n=h+w
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod % i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod
 
ans=0
while a<h and b<w:
    ans=(ans+cmb(h-1-a+b,b)*cmb(w-1-b+a,a))%mod
    a+=1
    b+=1
print(ans)

Solution (Python):
class Combination:
    def __init__(self, size=100, 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, size + 2):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

    def ncr(self, n, 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 sol():
    H, W, A, B = map(int, input().split())
    MOD = 10**9 + 7

    comb = Combination(H + W + 100)

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

    print(ans)


sol()

Solution (Python):
H, W, A, B = map(int, input().split())
MAX = 200000
MOD = 1000000007
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX
fac[0] = 1
fac[1] = 1
finv[0] = 1
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  

r = 0
for i in range(B, W):
  r += fac[H-A-1+i]*(finv[H-A-1]*finv[i]%MOD)%MOD * fac[A+W-i-2]*(finv[A-1]*finv[W-1-i]%MOD)%MOD
  r = r%MOD
print(r)

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

Solution (Python):
high, width, y, x = map(int, input().split())

def nCr(n, r):
    return ((((fact[n]*finv[n-r])%mod)*finv[r])%mod)

mod = 10**9 + 7
inv = mod - 2
maxn = high + width - 2
fact = [0] * (maxn+1)
finv = [0] * (maxn+1)
fact[0] = fact[1] = 1
finv[0] = finv[1] = 1


for i in range(2, maxn+1):
    fact[i] = (fact[i-1] * i) % mod


for i in range(2, maxn+1):
    finv[i] = pow(fact[i], inv, mod)

route = 0
for i in range(1, high-y+1):
        route += (nCr(x+i-2, i-1) * nCr(width+high-x-1-i, high-i)) % mod
        route = route % mod
print(int(route))

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

SIZE = h+w+2
MOD = 10**9 + 7
MOD_Farmer = 10**9+5

fact = [0] * SIZE
inv = [0] * SIZE
fact_inv = [0] * SIZE


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




def comb( n, r ):
  if r >= 0 and n >= 0:
    return fact[n] * fact_inv[n-r]%MOD * fact_inv[r]%MOD
  else :
    return 0.0




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

Solution (Python):
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
h,w,a,b=map(int,input().split())
n=h+w
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod % i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

ans=0
while a<h and b<w:
    ans=(ans+cmb(h-1-a+b,b)*cmb(w-1-b+a,a))%mod
    a+=1
    b+=1
print(ans)

Solution (Python):
h,w,a,b=map(int,input().split())
n_func=[None for _ in [0]*200001]
n_func[0]=1
for i in range(1,200001):
    n_func[i]=(i*n_func[i-1])%(10**9+7)
def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
def nCr(n,r,mod=10**9+7):return inv_n(n_func[n-r]*n_func[r]%mod,mod)*n_func[n]%mod

cnt=0
for i in range(h-a):
    cnt=(cnt+nCr(i+b-1,b-1)*nCr(h+w-b-i-2,w-b-1))%(10**9+7)
print(cnt)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

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

def comb(n,r):
    return fact[n] * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod) % mod
ans = 0
for i in range(b,w):
    x = comb(h-a-1+i,i)*comb(a-1+w-i-1,a-1) % mod
    ans += x
    ans %= mod
print(ans)

Solution (Python):
MOD=10**9+7
fact=[1]
temp=1
for i in range(1,3*10**5+1):
    temp*=i
    temp%=MOD
    fact+=[temp]

def bino(a,b):
    if a<b:
        return 0
    up=fact[a]
    down=fact[a-b]*fact[b]
    return (up*pow(down,MOD-2,MOD))%MOD

def find(H,W,A,B):
    temp=0
    for x in range(1,H-A+1):
        temp+=bino(x+B-2,x-1)*bino(W-B-1+H-x,H-x)
        temp%=MOD
    return temp

H,W,A,B=list(map(int,input().strip().split(" ")))
print(find(H,W,A,B))

Solution (Python):


SIZE=200001; MOD=10**9+7 

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

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

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

h,w,a,b = [int(i) for i in readline().split()]


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

print(ans)

Solution (Python):

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

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

MOD = 10 ** 9 + 7


first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) * modinv(i, MOD)) % MOD
    first.append(tmp)




second = []
for i in range(0, H):
    if i == 0:
        tmp = 1
        second.append(tmp)
        continue
    tmp = (tmp * ((W - B) + i - 1) * modinv(i, MOD)) % MOD
    second.append(tmp)




ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - 1 -i]) % MOD

print (ans)

Solution (Python):
H,W,A,B=map(int,input().split())
N=H+W
mod=10**9+7
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]
ans=0
for i in range(H-A):
    ans+=Comb(B+i-1,i)*Comb((W-B-1)+(H-i-1), H-i-1)
    ans%=mod
print(ans)

Solution (Python):
import math

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

inp = input().split(' ')
inpint = [int(i) for i in inp]
h = inpint[0]
w = inpint[1]
a = inpint[2]
b = inpint[3]

xfac = [0 for r in range(h+w-2)]
xfac_inv = [0 for r in range(h+w-2)]

for i in range(h+w-2):
	if i == 0:
		xfac[i] = 1
	else:
		xfac[i] = (xfac[i-1]*i)%1000000007

for i in reversed(range(h+w-2)):
	if i == h+w-3:
		xfac_inv[i] = modinv(math.factorial(i),1000000007)
	else:
		xfac_inv[i] = xfac_inv[i+1] * (i+1) % 1000000007







def com(a,b):
	return (xfac[a] * xfac_inv[b] * xfac_inv[a-b])%1000000007

sum = 0
for i in range(b,w):
	sum += com(i + h-a-1,h-a-1) * com((a-1)+w-i-1, w-i-1)
	sum %= 1000000007

print(sum)

Solution (Python):
def frac_with_mod(a,m):
    outlist = [ 1 for i in range(a+1) ]
    for i in range(1,a+1):
        outlist[i] = (outlist[i-1] * i)% m
    return outlist

frac_list = frac_with_mod(2*10**5,10**9+7)

def comb_with_mod(a,b,m):
    global frac_list
    return ( frac_list[a+b-2] * pow(frac_list[a-1],m-2,m) * pow(frac_list[b-1],m-2,m) ) % m

mod = 10**9+7
h, w, a, b = [ int(v) for v in input().split() ]

c = h - a
d = w - b


if c == 1:
    waypoint_list = [ 1 for i in range(d) ]
else:
    waypoint_list = [ comb_with_mod(b+1+i,c-1,mod) for i in range(d) ]
    s = comb_with_mod(b,c,mod)

    for i in range(d):
        waypoint_list[i] = ( s + waypoint_list[i] ) % mod
        s = waypoint_list[i]
        waypoint_list[i] = ( comb_with_mod(a,d-i,mod) * waypoint_list[i] ) % mod

print(sum(waypoint_list)%mod)

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

fac = [1] * (H + W + 1)
x = 1
for i in range(1, H + W + 1):
    x *= i
    x %= p
    fac[i] = x

ifac = [1] * (H + W + 1)
x = fac[H + W]
q = p - 2

while q > 0:
    if q & 1:
        ifac[H + W] *= x % p
    x *= x % p
    q >>= 1

for i in range(H + W - 1, 0, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % p

def com(a, b):
    return (fac[a] * ifac[b] * ifac[a-b]) % p

ans = 0

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

print(ans)

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


def inv(k):
    return pow(k, M - 2, M)


def comb(n, k):
    if n < k:
        return 0
    elif k == 0:
        return 1
    else:
        r = 1
        for i in range(k):
            r = (r * ((n - i) * inv(k - i)) % M) % M
        return r


ans = comb(h + w - 2, h - 1)

if a == 1 and b == 1:
    ans -= 1
elif a == 1:
    ans -= comb(h + b - 2, h - 1)
elif b == 1:
    ans -= comb(w + a - 2, w - 1)
else:

    memo = [1] * b
    for i in range(1, b):
        memo[i] = (memo[i - 1] * (h - a + i) * inv(i)) % M

    memo2 = [0] * b
    height = a - 1
    width = w - b
    memo2[b - 1] = comb(height + width, height)
    for i in range(1, b):
        memo2[b - i - 1] = (memo2[b - i] * (height + width + i) * inv(width + i)) % M

    ans -= memo[0] * memo2[0]
    ans %= M
    for i in range(1, b):
        ans -= (memo[i] - memo[i - 1]) * memo2[i]
        ans %= M

print(ans % M)

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

MOD = 10 ** 9 + 7
f = [1] * 300005
for i in range(2, 300005):
    f[i] = (f[i - 1] * i) % MOD

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

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

Solution (Python):
mod = 10**9 + 7
N = 200000
fact = [None] * (N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i % mod

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

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

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

fac = [1]
inv = [1]

for i in range(1, H+W+1) :
    fac.append(fac[-1] * i % MOD)
    inv.append(pow(fac[-1], MOD - 2, MOD))
    
ret = 0
for i in range(H-A) :
    ret += fac[i+B-1]*inv[i]*inv[B-1]*fac[H+W-i-B-2]*inv[H-i-1]*inv[W-B-1]%MOD
    ret %= MOD
    
print(ret)

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))










def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret

def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


factorials = get_factorials(H + W, MOD)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    return factorials[n] * mod_inv(factorials[r], mod) * mod_inv(factorials[n - r], mod) % mod


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