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):
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         
        self.inverse = {i: None for i in range(1, N+1)}   
        self.fact_inverse = {i: None for i in range(N+1)} 
        
        
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)

H, W, A, B = map(int, input().split())
MOD = 10**9 + 7
com = Combinatorics(H+W, MOD)
ans = com.binom(H-1+W-1, H-1)
for j in range(B):
    ans = (ans - com.binom(H-A-1+j, j) * com.binom(A-1+W-j-1, A-1)) % MOD
print(ans)

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())



def inv_mod(n: int, mod: int) -> list:
    inv = [0, 1]
    for i in range(2, n + 1):
        inv.append(mod - ((mod // i) * inv[mod % i]) % mod)
    return inv



def fact(n: int, mod: int) -> list:
    fac = [1, 1]
    res = 1
    for i in range(2, n + 1):
        res = res * i % mod
        fac.append(res)
    return fac



def fact_inv(n: int, inv: list, mod: int) -> list:
    facInv = [1, 1]
    for i in range(2, n + 1):
        facInv.append(facInv[i - 1] * inv[i] % mod)
    return facInv



def nCr(n: int, r: int, mod: int, fac: list, facInv: list) -> int:
    if not (0 <= r and r <= n):
        return 0

    return ((fac[n] * facInv[r]) % mod) * facInv[n - r] % mod


def get_gates(h, w, a, b):
    i = 0
    gates = []
    while h-a-1-i >= 0 and b+i < w:
        gates.append((h-a-1-i, b+i))
        i += 1

    return gates


h, w, a, b = li()
MOD = 10**9 + 7

gates = get_gates(h,w,a,b)

inv = inv_mod(h+w, MOD)
fac = fact(h+w, MOD)
facInv = fact_inv(h+w, inv, MOD)

ans = 0
for ri, ci in gates:
    ans += nCr(ri+ci, ci , MOD, fac, facInv) * nCr(h+w-2-(ri+ci), w-1-ci, MOD, fac, facInv)
    ans %= MOD

print(ans)

Solution (Python):
H,W,A,B=map(int,input().split())
mod=10**9+7
kaijo=[0]*(H+W+1)
kaijo[0]=1
for i in range(1,H+W+1):
    kaijo[i]=(kaijo[i-1]*i)%mod
gyaku=[0]*(H+W+1)
gyaku[H+W]=pow(kaijo[H+W],mod-2,mod)
for i in range(H+W,0,-1):
    gyaku[i-1]=(gyaku[i]*i)%mod
def conb(x,k):
    return (kaijo[x]*gyaku[k]*gyaku[x-k])%mod
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))%mod
print(ans)

Solution (Python):
H,W,A,B=map(int,input().split())
mod=10**9+7
kaijo=[0]*(H+W+1)
kaijo[0]=1
for i in range(1,H+W+1):
    kaijo[i]=(kaijo[i-1]*i)%mod
gyaku=[0]*(H+W+1)
gyaku[H+W]=pow(kaijo[H+W],mod-2,mod)
for i in range(H+W,0,-1):
    gyaku[i-1]=(gyaku[i]*i)%mod
def conb(x,k):
    return (kaijo[x]*gyaku[k]*gyaku[x-k])%mod
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))%mod
print(ans)

Solution (Python):




max_value = 500050
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]


def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

    for i in range(2, max_value):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod


def main():
    h, w, a, b = map(int, input().split())
    x = h - (a + 1)
    com_init()
    prev = 0
    ans = 0
    com_xy = [0 for _ in range(w - b)]
    com_za = [0 for _ in range(w - b)]
    i = 0
    j = 0

    for y in range(b, w):
        com_xy[i] = com(x + y, y)
        i += 1

    for z in range((w - (b + 1) + a), a - 1, -1):
        com_za[j] = com(z, z - a)
        j += 1

    for xy, za in zip(com_xy, com_za):
        ans += (xy - prev) * za
        ans %= mod
        prev = xy

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W,A,B = map(int,input().split())
fac = [0]*(H+W)
finv = [0]*(H+W)
inv = [0]*(H+W)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,H+W):
        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,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
ans = 0
for x in range(W-B):
    if x == 0:
        ans += ((comb(H-A-1+B+x,B+x))*comb(A+W-1-B-x,A))
    else:
        ans += ((comb(H-A-1+B+x,B+x)-comb(H-A-1+B+x-1,B+x-1))*comb(A+W-1-B-x,A))
    ans %= mod
print(ans)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W,A,B = map(int,input().split())
fac = [0]*(H+W)
finv = [0]*(H+W)
inv = [0]*(H+W)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,H+W):
        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,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
ans = 0
for x in range(W-B):
    if x == 0:
        ans += ((comb(H-A-1+B+x,B+x))*comb(A+W-1-B-x,A))
    else:
        ans += ((comb(H-A-1+B+x,B+x)-comb(H-A-1+B+x-1,B+x-1))*comb(A+W-1-B-x,A))
    ans %= mod
print(ans)

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


MOD = 10 ** 9 + 7
M = 200005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

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


def comb(n, k):
    return fact[n] * rfact[n - k] * rfact[k] % MOD


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

print(ans)

Solution (Python):

import sys

MOD = 1000000007  

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

    F = [0] * (H + W + 1)
    F[0] = 1
    for i in range(1, H + W + 1):
        F[i] = (F[i-1] * i) % MOD
    F2 = [0] * (H + W + 1)
    F2[0] = 1
    for i in range(1, H+W+1):
        F2[i] = (F2[i-1] * pow(i, MOD-2, MOD)) % MOD
    def nck(a, b):
        if a == 0 and b == 0:
            return 1
        return (F2[a-b] * F2[b] % MOD) * F[a] % MOD
    total = nck(H+W-2, H-1)
    removed = 0
    for k in range(A):
        removed += nck(H-k-1+B-1, H-k-1) * nck(k+W-B-1, k)
        removed %= MOD
    res = (total - removed) % MOD
    print(res)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 1000000007
H, W, A, B = map(int, input().split())
if H - A > W - B:
    H, W = W, H
    A, B = B, A

ans1 = [1]
for i in range(H - A - 1):
    
    ans1.append((ans1[-1] * (H - A - 1 + B - i) * pow(i + 1, MOD - 2, MOD)) % MOD)

c = 1
for i in range(W - H + A - B):
    c = (c * (W - B - 1 + A - i) * pow(i + 1, MOD - 2, MOD)) % MOD
ans = c
for i in range(H - A - 1):
    
    c = (c * (H - 1 - i) * pow(W - H + A - B + 1 + i, MOD - 2, MOD)) % MOD
    ans = (ans + c * ans1[i + 1]) % MOD
print(ans)

Solution (Python):
MOD = 1000000007
H, W, A, B = map(int, input().split())
if H - A > W - B:
    H, W = W, H
    A, B = B, A

ans1 = [1]
for i in range(H - A - 1):
    
    ans1.append((ans1[-1] * (H - A - 1 + B - i) * pow(i + 1, MOD - 2, MOD)) % MOD)

c = 1
for i in range(W - H + A - B):
    c = (c * (W - B - 1 + A - i) * pow(i + 1, MOD - 2, MOD)) % MOD
ans = c
for i in range(H - A - 1):
    
    c = (c * (H - 1 - i) * pow(W - H + A - B + 1 + i, MOD - 2, MOD)) % MOD
    ans = (ans + c * ans1[i + 1]) % MOD
print(ans)

Solution (Python):
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]
 
    def __init__(self, mod  = 10**9+7, max_n = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append
 
        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)
 
        inv_append(pow(fac[-1], mod-2, mod))
 
        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)
 
        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]
 
    def get_combination(self, n, r):
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod
 
    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod
 
 
import math
Big = BigCombination()
mod=10**9+7
h,w,a,b=map(int,input().split())
ans=0
for i in range(b,w):
    ans=(ans+ Big.get_combination(h-a-1+i,i)* Big.get_combination(a-1+w-i-1,w-i-1))%mod
print(ans)

Solution (Python):
H, W, A, B = map(int, input().split())
MAX = H + W
MOD = 10 ** 9 + 7
fac = [0 for _ in range(MAX)]
finv = [0 for _ in range(MAX)]
inv = [0 for _ in range(MAX)]
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD


def COM(n, k):
    global fac
    global finv
    global MOD
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def route(h, w):
    return COM(h + w - 2, h - 1)


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

Solution (Python):
class COMB_MOD():
    
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod
mod = 10**9 + 7
h,w,a,b = map(int,input().split())
C = COMB_MOD(max_n=2*10**5)
ans = 0
for i in range(h-a):
    ans = (ans + C.comb(b-1+i,i)*C.comb(h-1-i+w-1-b,h-1-i))%mod
print(ans)

Solution (Python):

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res


def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    



def mod_comb(n,k):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    
    if e1 > e2 + e3:
        return 0

    
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p


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

p = 10**9+7

fact = [1]
k = 1
for i in range(1,10**6+10):
    k = k*i%p
    fact.append(k)

res = 0
for i in range(h-a):
    res += mod_comb(i+b-1,b-1)*mod_comb(h-i-1+w-b-1,w-b-1)
    res = res%p
print(res)

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


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


class Fact():
    def __init__(self, H, W):
        self.mod = 10**9+7
        self.facts = [1]*(H+W-1)
        for i in range(1, H+W-1):
            self.facts[i] = self.facts[i-1]*i % mod

        self.i = [pow(self.facts[-1], mod-2, mod)]
        for i in range(1, H+W-1)[::-1]:
            self.i.append(self.i[-1]*i % mod)
        self.i.reverse()

    def comb(self, n, r):
        ret = self.facts[n] * self.i[n-r]*self.i[r]
        return ret

    def print_fact(self):
        print(self.facts)


f = Fact(H, W)

all_path = f.comb(H+W-2, H-1)

remove_path = 0
for i in range(B):
    tmp = f.comb(H-A+i-1, i)
    tmp *= f.comb(W-i-1+A-1, A-1)
    remove_path += tmp

remove_path %= mod

print((all_path - remove_path) % mod)

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

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

Solution (Python):
mod = 1000000007
H, W, A, B = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
factorial = [1]
for n in range(1, H+W):
    factorial.append(factorial[n-1]*n % 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
inverseFactorial = [0 for i in range(H+W)]
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in range(H+W-2, -1, -1):
    inverseFactorial[n] = (inverseFactorial[n+1] * (n+1) )% mod

def combi(n, m):
    return (factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] )% mod
 
sum = 0
for i in range(B+1, W+1):
    sum = (sum + combi(H-A-1+i-1, i-1) * combi(A-1+W-i, W-i)) % mod
print(sum)

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

def Power(i, n):
    if n == 1:
        return i
    else:
        if n%2 == 0:
            return Power((i*i)%mod, n//2)
        else:
            return (Power((i*i)%mod, n//2) * i) % mod

NF = [1 for i in range(H+W+1)]
for i in range(2, H+W+1):
    NF[i] = (NF[i-1] * i) % mod

NFI = [1 for i in range(H+W+1)]
NFI[H+W] = Power(NF[-1], mod-2)
for i in reversed(range(1, H+W)):
    NFI[i] = (NFI[i+1] * (i+1)) % mod

Ans = 0
for w in range(B, W):
    upper = (NF[H-A+w-1] * NFI[w] * NFI[H-A-1]) % mod
    lower = (NF[W+A-w-2] * NFI[A-1] * NFI[W-w-1]) % mod
    Ans += upper * lower % mod
    Ans %= mod
print(Ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]

mod = 10**9+7
H, W, A, B = inpl()
fac = [1 for _ in range(H+W-1)]
for i in range(H+W-2):
    fac[i+1] = (i+1)*fac[i]%mod

inv = [1 for _ in range(H+W-1)]
for i in range(2,H+W-2):
    inv[i] = (-(mod//i) * inv[mod%i]) %mod    

facinv = [1 for _ in range(H+W-1)]
for i in range(H+W-2):
    facinv[i+1] = inv[i+1]*facinv[i]%mod


ans = 0
for i in range(W-B):
    ans += (fac[H+B-A-1+i] * fac[W+A-B-2-i] * facinv[H-A-1] * facinv[B+i]\
    * facinv[A-1] * facinv[W-B-1-i] )%mod
print(ans%mod)

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

u = {}
for i in range(B, W):
    t = fact[i + H - A - 1] * pow(fact[i] * fact[H - A - 1], MOD - 2, MOD)
    u[i + 1] = t % MOD

ans = 0
for k, v in u.items():
    t = fact[W - k + A - 1] * pow(fact[W - k] * fact[A - 1], MOD - 2, MOD) % MOD
    ans = (ans + t * v) % MOD

print(ans)

Solution (Python):


MOD = 1000000007
fact = []

def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)

def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, min(dx, dy))
    return count

def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li

def combi(n, k):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % MOD
    return (numera * inv(denomi)) % MOD

def init_fact(maxn):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % MOD)

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

def pow(n, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2)
        return (x * x) % MOD
    else:
        x = pow(n, p - 1)
        return (x * n) % MOD

main()

Solution (Python):

 
import functools
 
MOD = 1000000007
fact = []
 
def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)
 
def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count
 
def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li
 
def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod
 
def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)
 
def inv(n, mod):
    return pow(n, mod - 2, mod)
 
def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod
 
main()

Solution (Python):
ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


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


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2
ans %= mod

for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) * inv(b + i) % mod
    c2 = c2 * (bb - i + 1) * inv(a + bb - i) % mod
    ans += c1 * c2
    ans %= mod
print(ans)

Solution (Python):
H, W, A, B = map(int, input().split())
MOD = 10**9 + 7
c1 = []
c2 = []
for i in range(H-A):
    if i == 0:
        c1.append(1)
        c2.append(1)
    else:
        m = pow(i, MOD-2, MOD)
        t1 = (c1[i-1]*(B-1+i) % MOD) * m
        c1.append(t1 % MOD)
        t2 = (c2[i-1]*(W-B-1+i) % MOD) * m
        c2.append(t2 % MOD)
for i in range(H-A, H):
    t = (c2[i-1]*(W-B-1+i) % MOD) * pow(i, MOD-2, MOD)
    c2.append(t % MOD)
ans = 0
for i in range(len(c1)):
    ans += (c1[i]*c2[-i-1]) % MOD
print(ans % MOD)

Solution (Python):
import math
mod = 10**9+7
def inv(x):
	return pow(x,mod-2,mod)


MAX = 10**5*3
facts = [1 for i in range(MAX)]
invs = [1 for i in range(MAX)]


def factorial(x):
	for i in range(1,x):
		facts[i] = (facts[i-1] * i)% mod
		invs[i] = inv(facts[i])

factorial(MAX)
def nCr(n,r):
	return facts[n]*invs[r] * invs[n-r] % mod

h,w,th,ty = map(int,raw_input().split())

ans = 0

for i in range(ty+1,w+1):
	
	ans += (nCr(h-th-1 + i-1,i-1)%mod * nCr(th-1 + w-i,w-i)%mod)%mod

print ans%mod

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

M, S = 10 ** 9 + 7, H + W - 2
fact_n = [0 for i in range(S+1)]
fact_inv = [0 for j in range(S+1)]


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    res = fact_n[n] * fact_inv[r] % M
    return res * fact_inv[n-r] % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, S+1):
        fact_n[i] = fact_n[i-1] * i % M

    fact_inv[S] = pow(fact_n[S], M-2, M)
    for i in range(S-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

    com, bef = combination(S, H-1), 0
    for i in range(B):
        c1, c2 = combination(H-A+i, H-A), combination(S-H+A-i, A-1)
        tmp = (c1-bef) * c2 % M
        bef += c1 - bef
        com -= tmp
        if com < 0:
            com += M

    print(com)


if __name__ == '__main__':
    main()

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

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


N = H - 1
inv = [0] * (N + 1)
inv[1] = 1
for k in range(2, N + 1):
    inv[k] = (-(MOD // k) * inv[MOD % k]) % MOD


n1 = B - 1
C1s = [0] * (H - A)
C1s[0] = 1
for r in range(1, H - A):
    C1s[r] = (C1s[r - 1] * (n1 + r) * inv[r]) % MOD


n2 = W - B - 1
C2s = [0] * H
C2s[0] = 1
for r in range(1, H):
    C2s[r] = (C2s[r - 1] * (n2 + r) * inv[r]) % MOD

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

print(ans)

Solution (Python):
h, w, a, b = map(int, raw_input().split())
p = 10 ** 9 + 7
z = 0
s = 1
for i in range(w - b - 1):
	s = s * (h + w - b - 2 - i) * pow(i + 1, p - 2, p) % p
for i in range(h - a):
	z = (z + s) % p
	s = s * (b + i) * (h - 1 - i) * pow((i + 1) * (h + w - b - 2 - i), p - 2, p) % p
print z

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

count = 0

factoriallist = [1]*(H+W)
for i in range(1,H+W):
    factoriallist[i] = factoriallist[i-1]*i % mod


inverse_factoriallist = [0]*(H+W)
inverse_factoriallist[H+W-1] = pow(factoriallist[H+W-1],mod-2,mod)

for i in range(H+W-2,-1,-1):
    
    inverse_factoriallist[i] = inverse_factoriallist[i+1] * (i+1) % mod
    


for i in range(B, W):
    count += ((factoriallist[H-A+i-1] * inverse_factoriallist[H-A-1] * inverse_factoriallist[i] )%mod) * ((factoriallist[A+(W-i) -2] * inverse_factoriallist[A-1] * inverse_factoriallist[W-i-1])%mod)

print(int(count% mod))

Solution (Python):
M = 1000000007
H,W,A,B = map(int,input().split())
factorial_list = [0] * (H+W)
factorial_list[0] = 1
for i in range(1,H+W):
    factorial_list[i] = factorial_list[i-1]*i %M
inverse_factorial_list = [0] * (H+W)

def power(a,n):
    if n == 0:
        return 1
    if n == 1:
        return a % M
    if n % 2 == 0:
        return power(a,n//2)**2 % M
    return (power(a,n-1) * a) % M

inverse_factorial_list[H+W-1] = power(factorial_list[H+W-1],M-2)
for i in range(H+W-2,-1,-1):
    inverse_factorial_list[i] = inverse_factorial_list[i+1] *(i+1) %M

def C(a,b):
    return factorial_list[a+b] * inverse_factorial_list[a] * inverse_factorial_list[b] % M
    
route = 0
for i in range(B,W):
    a = H - A - 1
    b =  i
    c = A - 1
    d = W - i - 1
    route += ((C(a,b)%M) * (C(c,d)%M)) 
    route %= M

print(route)

Solution (Python):
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
H,W,A,B=map(int,input().split())
N=H+W
fact=[0 for i in range(N+1)]
finv=[0 for i in range(N+1)]
fact[0]=1
finv[0]=1
for i in range(1,N+1):
    fact[i]=(fact[i-1]*i)%P
    finv[i]=(inv(fact[i]))%P
def C(a,b):
    return (fact[a+b]*(finv[a]*finv[b])%P)%P
D=0
for i in range(B,W):
    K=(C(H-A-1,i)*C(A-1,W-1-i))%P
    D=(D+K)%P
print(D)
'''
HWAB
6734
4   C(2,4)*C(2,2)   15*6=90
5   C(2,5)*C(2,1)   21*3=63
6   C(2,6)*C(2,0)   28*1=28

'''

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

f_list = [1] * 200000
f_r_list = [1] * 200000

for i in range(199999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % BIG)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % BIG), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % BIG)

f_r_list[-1] = power(f_list[-1], BIG - 2)

for i in range(2, 200001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (200002 - i)) % BIG)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % BIG) * f_r_list[r - 1]) % BIG 

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

ans = 0

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

print(int(ans))

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




def fact(N, P):
    ret = [1] * (N + 1)
    for n in range(2, N+1):
        ret[n] = (ret[n-1] * n) % P

    return ret



def pow_r(a, b, P):
    """
    O(log n)
    """
    if b == 0:  
        return 1
    if b % 2 == 0:  
        return pow_r((a ** 2) % P, b // 2, P)
    else:  
        return (a * pow_r((a ** 2) % P, (b - 1) // 2, P)) % P


def inv_fact(N, P):
    ret = [1] * (N + 1)
    fac = fact(N, P)
    ret[N] = pow_r(fac[N], P - 2, P)
    for n in reversed(range(2, N)):
        ret[n] = (ret[n + 1] * (n + 1)) % P

    return ret


fac = fact(N, P)
inv = inv_fact(N, P)

def combination(n, r, P):
    return (fac[n] * inv[r] * inv[n - r]) % P



sub = 0
for a in range(A):
    sub = (sub + combination((H - 1 - a) + (B - 1), B - 1, P) * combination(a + (W - 1 - B), a, P)) % P

print((combination((H - 1) + (W - 1), H - 1, P) - sub) % P)

Solution (Python):
h,w,a,b=[int(x)for x in raw_input().split()]
m=1000000007
def f(*n):
 r=1
 for i in xrange(*n):r=r*(i+1)%m
 return r
def g(n):return pow(n,m-2,m)
c=s=f(w-b-1,h+w-b-2)*g(f(h-1))%m
for i in xrange(1,h-a):
 s=s*(b+i-1)%m*(h-i)%m*g(i*(h+w-b-1-i)%m)%m
 c=(c+s)%m
print c

Solution (Python):
MOD=10**9+7
fact=[1 for i in range(200010)]
ifact=[1 for i in range(200010)]
for i in range(2,200010):
    fact[i]=(fact[i-1]*i)%MOD
    ifact[i]=(ifact[i-1]*pow(i,MOD-2,MOD))%MOD
def nCm(n,m):
    global MOD,fact,ifact
    return (fact[n]*((ifact[m]*ifact[n-m])%MOD))%MOD
h,w,a,b=map(int,input().split())
ret=0
for i in range(h-a):
    ret+=(nCm(i+b-1,i)*nCm((h-i-1)+(w-b-1),h-i-1))%MOD
    ret%=MOD
print(ret)

Solution (Python):


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

fct = [1]
inv = [1]
for i in range(1, H + W - 1):
    fct.append((fct[-1] * i) % mod)
    inv.append(pow(fct[i], mod - 2, mod))

def comb(n, k):
    return (fct[n] * inv[n - k] * inv[k]) % mod

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

Solution (Python):


mod = 10**9 + 7

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

def comb(n, k):
    res = 1
    for i in range(k):
        res = (res * (n - i) * inv(i + 1)) % mod
    return res

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

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

Solution (Python):
MOD = 1000000007
kaijo = []
kaijo_1 = []

def power(a, n):
    if (n == 0):
        return 1
    res = 1
    while (n > 0):
        if ((n & 1) == 1):
            res = res * a % MOD
        a = a * a % MOD
        n >>= 1
    
    return res    

def calcKaijo():
    kaijo.append(1)
    for i in range(1, 200001):
        kaijo.append((kaijo[i - 1] * i) % MOD)

def calcKaijo_1():
    for i in range(200001):
        kaijo_1.append(0)
    kaijo_1[200000] = power(kaijo[i], MOD - 2)
    for i in range(199999, -1, -1):
        kaijo_1[i] = kaijo_1[i + 1] * (i + 1) % MOD

def comb(n, r):
    return kaijo[n] * kaijo_1[n - r] * kaijo_1[r]

calcKaijo()
calcKaijo_1()
h, w, a, b = [int(i) for i in input().split()]
count = 0
for i in range(b, w):
    count += comb(h - a - 1 + i, i) * comb(a - 1 + w - 1 - i, w - 1 - i)
    count %= MOD

print(count)