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
input = sys.stdin.readline


class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


def main():
    h,w,a,b = map(int,input().split())
    cmb = Combination(10**6)
    roop = min(h-a,w-b)
    ans = 0
    for i in range(roop):
        before = cmb(h-a+b-1,b+i) % (10**9+7)
        after  = cmb(w+a-b-1,a+i) % (10**9+7)
        ans  = (ans+(before*after)%(10**9+7)) % (10**9+7)
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):

mod=10**9+7
MAX=2*10**5+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

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

print(ans)

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

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

    
    def comb_mod(n, r, p):
        return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

    for i in range(H-A):
        ans += comb_mod(i+B-1,B-1,mod) * comb_mod(H-1-i+W-B-1,W-B-1,mod)

    print(ans%mod)

if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10 ** 9 + 7
fac = [1] * 200005
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
h, w, a, b = map(int, input().split())
ans = 0
x, y = b, h - a - 1
while x < w and y >= 0:
    p = w - x - 1
    q = h - y - 1
    ans += (fac[x + y] * pow(fac[x] * fac[y], MOD - 2, MOD) *
            fac[p + q] * pow(fac[p] * fac[q], MOD - 2, MOD)) % MOD
    x += 1
    y -= 1
print(ans % MOD)

Solution (Python):
n=200000
mod=10**9+7
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
h,w,a,b=map(int,input().split())
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)

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

N = H+W+1

def power(base, num):
    if num == 0:
        return 1
    elif num % 2==0:
        return power(base, num//2) **2 % MOD
    elif num==1:
        return base % MOD
    else:
        return power(base, num//2) **2 * base % MOD

fact = [0 for i in range(N)]
inv_fact = [0 for i in range(N)]

fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i-1] * i % MOD
    
inv_fact[H+W] = power(fact[H+W], MOD-2)
for i in range(1, N):
    inv_fact[N-1-i] = inv_fact[N-i] * (N-i) % MOD

    
def comb(x,y):
    return (fact[x] * inv_fact[y])%MOD * inv_fact[x-y] % MOD

ans = 0

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

Solution (Python):
def examD(mod):
    class combination():
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

    H, W, A, B =LI()
    N = H + W
    C = combination(N,mod)
    ans = C.comb(W+H-B-2, H-1,mod)
    pre = 1
    for i in range(1, H-A):
        ans += (C.comb(B+i,i,mod)-pre)*C.comb(W+H-B-2-i, H-1-i,mod)%mod
        ans %= mod
        pre = C.comb(B+i, i,mod)
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

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

mod = 10**9+7 
N = h+w
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

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

def 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

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

Solution (Python):

import sys
input = sys.stdin.readline


def init_fact(n,mod):
    fact,finv,inv = [1]*n,[1]*n,[1]*n
    for i in range(2,n):
        fact[i] = (fact[i-1]*i) % mod
        inv[i]  = mod - inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1] * inv[i] % mod
    return (fact,finv,inv)

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


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

modulo = 10**9+7
fact,finv,inv = init_fact(200000,modulo)

ans = 0
for i in range(H-A):
    ans += nCr(i+B-1,i,modulo,fact,finv) * nCr(H-i-1+W-B-1,W-B-1,modulo,fact,finv)
    ans %= modulo

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)


def extgcd(a, b):
    x, y = 0, 0

    def f(a, b):
        nonlocal x, y
        if b == 0:
            x = 1
            y = 0

            return a

        g = f(b, a % b)
        q = a // b
        next_x = y
        y = x - q * y
        x = next_x
        return g

    g = f(a, b)
    return x, y, g


fact = [0] * 200010
invfact = [0] * 200010
mod = 10 ** 9 + 7


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


fact[0] = 1
for i in range(1, 200000 + 1):
    fact[i] = (fact[i - 1] * i) % mod
for i in range(200000 + 1):
    x, y, g = extgcd(fact[i], mod)
    while x < 0:
        x += mod
    invfact[i] = x % mod

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

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

Solution (Python):

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

M = H+W-1
fact = [1 for i in range(M)]
for i in range(M):
    if i == 0:
        pass
    else:
        fact[i] = (fact[i-1]*i)%mod
        
refact = [1 for i in range(M)]
m = mod-2
b = bin(m)
b = b.lstrip("0b")
b = b[::-1]
m2 = len(b)
for i in range(M):    
    flog = [0 for j in range(m2)]
    for j in range(m2):
        if j == 0:
            flog[0] = fact[i]
        else:
            flog[j] = (flog[j-1]**2)%mod
    
    for j in range(m2):
        if b[j] == "1":
            refact[i]*=flog[j]
            refact[i]%=mod
            
row = B
wide = W-B
ans = 0
for i in range(wide):
    row = B+i
    C1 = (fact[H-A+row-1]*refact[H-A-1]*refact[row])%mod
    C2 = (fact[W+A-row-2]*refact[W-row-1]*refact[A-1])%mod
    
    ans+=C1*C2
    ans%=mod




print(ans)

Solution (Python):

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

M = H+W-1
fact = [1 for i in range(M)]
for i in range(M):
    if i == 0:
        pass
    else:
        fact[i] = (fact[i-1]*i)%mod
        
refact = [1 for i in range(M)]
m = mod-2
b = bin(m)
b = b.lstrip("0b")
b = b[::-1]
m2 = len(b)
for i in range(M):    
    flog = [0 for j in range(m2)]
    for j in range(m2):
        if j == 0:
            flog[0] = fact[i]
        else:
            flog[j] = (flog[j-1]**2)%mod
    
    for j in range(m2):
        if b[j] == "1":
            refact[i]*=flog[j]
            refact[i]%=mod
            
row = B
wide = W-B
ans = 0
for i in range(wide):
    row = B+i
    C1 = (fact[H-A+row-1]*refact[H-A-1]*refact[row])%mod
    C2 = (fact[W+A-row-2]*refact[W-row-1]*refact[A-1])%mod
    
    ans+=C1*C2
    ans%=mod




print(ans)

Solution (Python):
import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N= [0]*(H+W)
N[H+W-1] = power(M[H+W-1], e-2)
for i in range(H+W-2, -1, -1):
    N[i] = N[i+1] * (i+1) % e

def c(a,b):
    return M[a]*N[b]*N[a-b]%e

T = 0
for i in range(W-B):
    P = c(H+W-A-i-2,H-A-1)
    Q = c(A+i-1,i)
    T = (T + P*Q)
print(T%e)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
mod = 1000000007


h, w, a, b = LI()
n = h + w

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


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


print(ans)

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

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

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

inverse_stairs = [0]*(h+w)
inverse_stairs[h+w-1] = modpow(stairs[h+w-1], mod-2)
for i in range(h+w-2, -1, -1):
    inverse_stairs[i] = inverse_stairs[i+1] * (i+1) % mod
    
ret = 0
for i in range(w-b):
    com = stairs[w-i+h-a-2]%mod
    com = com*inverse_stairs[w-i-1]%mod
    com = com*inverse_stairs[h-a-1]%mod
    com = com*stairs[i+a-1]%mod
    com = com*inverse_stairs[i]%mod
    com = com*inverse_stairs[a-1]%mod
    ret += com

print(ret%mod)

Solution (Python):

cnt=0
h,w,a,b=map(int,input().split())
def find_power(n):
    
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist

def find_inv_power(n):
    
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

powlist=find_power(h+w+1)
invlist=find_inv_power(h+w+1)
def combi(n,r):
    a=powlist
    b=invlist
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(10**9+7)

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

Solution (Python):
MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            
            self.inverses.append(self.mod - self.inverses[self.mod % i] * (
                        self.mod // i) % self.mod)
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


def check(h, w, a, b):
    combination = ModCombination(mod=MOD, n_max=h + w)
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(combination, *d1)
        r2 = calc_routes(combination, *d2)
        routes = r1 * r2 % MOD
        all_routes += routes
        all_routes %= MOD
        p = (p[0] + 1, p[1] - 1)
    return all_routes


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

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



def mod_cmb(n, r, mod):
    x = fact[n] * fact_inverse[r] % mod
    x = x * fact_inverse[n - r] % mod
    return x


def d_cmb(n, r, mod):
    return mod_cmb(n + r - 1, r, mod)



def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


fact = [1] * (limit + 1)
fact_inverse = [1] * (limit + 1)

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

fact_inverse[limit] = mod_pow(fact[limit], MOD - 2, MOD)
for i in reversed(range(1, limit + 1)):
    fact_inverse[i - 1] = fact_inverse[i] * i % MOD

n1 = W
r1 = H - A - 1
n2 = 1
r2 = A - 1
ans = 0
for i in range(W - B):
    ans += d_cmb(n1 - i, r1, MOD) * d_cmb(n2 + i, r2, MOD)
    ans %= MOD

print(ans)

Solution (Python):
def modpow(a, n, mod):
  res = 1
  while n > 0:
    if (n & 1):
      res = res * a % mod
    a = a * a % mod
    n >>= 1
  return res

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



table = [1 for i in range(h + w + 1)]
inv_table = [1 for i in range(h + w + 1)]
temp = 1
for i in range(1, h + w + 1):
  temp = temp * i % DIV
  table[i] = temp
  inv_table[i] = modpow(temp, DIV - 2, DIV)

for i in range(w - b):
  n1 = table[h + i + b - a - 1] * inv_table[b + i] * inv_table[h - a - 1] % DIV
  n2 = table[w + a - b - 2 - i] * inv_table[a - 1] * inv_table[w - b - 1 - i] % DIV
  ans += n1 * n2 % DIV
ans = int(ans)
print(ans%DIV)

Solution (Python):
import operator as op
from functools import reduce

MOD = (10 ** 9) + 7

factors = [1, 1]
finv = [1, 1]
inv = [0, 1]

for i in range(2, 200010):
    factors.append(factors[i - 1] * i % MOD)
    inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)
    finv.append(finv[i - 1] * inv[i] % MOD)

def nck(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return factors[n] * (finv[k]  * finv[n - k] % MOD) % MOD

def ncr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

assert ncr(3, 4) == 0

def g(h, w, a, b):
    prev = [1] * w
    cur = [0] * w

    for i in range(h - 1):
        cur[0] = 1
        start = 0
        if i >= h - 1 - a:
            cur[b] = prev[b]
            start = b
        for j in range(start + 1, w):
            cur[j] = cur[j - 1] + prev[j]
            cur[j] = cur[j] % (1e9 + 7)
        prev, cur = cur, prev
    return prev[-1]

def f(H, W, A, B):
    count = 0
    x, y, a = H - A - 1, W + A - 2, A - 1
    for i in range(B, W): 
        c1 = nck(x + i, i)
        c2 = nck(y - i, a)
        c = c1 * c2
        count += c
        count = count % MOD
    return int(count)








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

Solution (Python):
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod
 
 
mod = 10**9+7 
N = 200000
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 = 0


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

print(ans)

Solution (Python):
MOD = 10**9 + 7
factorials = [1]
for i in range(1, 200000):
    factorials.append((factorials[-1] * i) % MOD)
invs = [pow(x, MOD - 2, MOD) for x in factorials]


def combinations(n, k):
    return (factorials[n] * invs[k] * invs[n - k]) % MOD


def f(x, y):
    return combinations(x + y - 2, x - 1)


h, w, a, b = map(int, input().split())
res = 0
for y in range(1, h - a + 1):
    res += (f(b, y) * f(w - b, h - y + 1)) % MOD
print(res % MOD)

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 = 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 )



H,W,A,B = map(int,input().split())
ret = 0
for i in range(H-A):
    ret += cmb(B-1+i, i, mod)*cmb(W-B-1+H-i-1, W-B-1,mod)
    
print(ret%(10**9+7))

Solution (Python):
def main():
    h,w,a,b=map(int,input().split(' '))
    mod = 10**9+7
    mx=max(h,w)
    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__':
    main()

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

ans = 0
for i in range(1, h-a+1):
    if i == 1:
        t1 = 1
        t2 = 1
        for j in range(1, ((h-a-i)+(b-1)+1)):
            t1 *= j
            t1 %= mod
        for j in range(1, ((b-1)+1)):
            t2 *= j
            t2 %= mod
        for j in range(1, ((h-a-i)+1)):
            t2 *= j
            t2 %= mod
        a1 = t1 * pow(t2, mod-2, mod) % mod

        t1 = 1
        t2 = 1
        for j in range(1, ((w-b-1)+(a+i-1)+1)):
            t1 *= j
            t1 %= mod
        for j in range(1, ((w-b-1)+1)):
            t2 *= j
            t2 %= mod
        for j in range(1, ((a+i-1)+1)):
            t2 *= j
            t2 %= mod
        a2 = t1 * pow(t2, mod-2, mod) % mod
    else:
        a1 *= pow((h-a-i)+(b-1)+1, mod-2, mod) 
        a1 *= h-a-i+1
        a1 %= mod 
        a2 *=  (w-b-1)+(a+i-1) 
        a2 %= mod
        a2 *= pow(a+i-1, mod-2, mod) 
        a2 %= mod
 
    
    ans += a1 * a2 
    ans %= mod

print(ans)

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(n, r, p):
  return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p


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

print(ans%mod)

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[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))



def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Solution (Python):
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I*(W+H-B-1-I))%M;Z+=C
print(Z%M)

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


conb1 = conb(h - a - 1 + b, b)
conb2 = conb(a + w - b - 1, a)
combi = conb1 * conb2
res = combi

for i in range(1, kai):
    res += conb(h - a - 1 + b, b + i) * conb(a + w - b - 1, a + i)

res %= mod
print(int(res))

Solution (Python):
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

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

mod = 10 ** 9 + 7
mc = ModComb(200010, mod=mod)

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

x, y, a = H - A - 1, W + A - 2, A - 1
print(sum(mc.nCk(x + i, i) * mc.nCk(y - i, a) for i in range(B, W)) % mod)

Solution (Python):
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    H,W,A,B = LI()

    ans = [0]*(W-B)

    ans[0] = 1

    for i in range(1,B+H-A):
        ans[0] *= i
        ans[0] %= mod
    for i in range(1,A-1+W-B):
        ans[0] *= i
        ans[0] %= mod
    for i in range(1,H-A):
        ans[0] *= pow(i,mod-2,mod)
        ans[0] %= mod
    for i in range(1,B+1):
        ans[0] *= pow(i,mod-2,mod)
        ans[0] %= mod
    for i in range(1,W-B):
        ans[0] *= pow(i,mod-2,mod)
        ans[0] %= mod
    for i in range(1,A):
        ans[0] *= pow(i,mod-2,mod)
        ans[0] %= mod

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

    return(sum(ans)%mod)


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

Solution (Python):
def d_iroha_and_a_grid(MOD=10**9 + 7):
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            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 comb(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    H, W, A, B = [int(i) for i in input().split()]
    c = Combination(max_n=H + W)
    
    
    
    ans = sum([c.comb(H - A - 1 + i, H - A - 1)
               * c.comb(A - 1 + W - 1 - i, A - 1) for i in range(B, W)])
    return ans % MOD

print(d_iroha_and_a_grid())

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

fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]

for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;

def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD

k = 1
ans = 0
while B+k <= W and H-A-k+1 > 0:
    ans += nCr(B+k-1+(H-A-k),B+k-1) * nCr(W-(B+k) + H-(H-A-k+1),H-(H-A-k+1))
    ans %= MOD
    k += 1
print(ans)

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


fact_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    fact_l[i] *= (fact_l[i-1]*i)%mod


factinv_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    factinv_l[i] = pow(fact_l[i],mod-2,mod)
    

point1 = [1 for i in range(w-b)]
for i in  range(len(point1)):
    yoko = b+i 
    tate = h-a-1
    n = yoko+tate
    r = yoko
    point1[i] = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod


out = 0
for i in range(len(point1)):
    yoko = w-b-i-1
    tate = a-1
    n = yoko+tate
    r = yoko
    case = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod
    out += (point1[i]*case)%mod
print(out%mod)

Solution (Python):

"""
Created on Mon Sep 23 17:33:45 2019
ABC042D
@author: maezawa
"""

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

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


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 HCOM(n,k):
    return COM(n+k-1,k)






h, w, a, b = list(map(int, input().split()))
cnt = 0
for i in range(h-a):
    p0 = HCOM(b, i) * HCOM(w-b,h-i-1)
    cnt = (cnt+p0)%MOD
print(cnt)

Solution (Python):
inp=input().split(" ")
H=int(inp[0])
W=int(inp[1])
A=int(inp[2])
B=int(inp[3])
mod=10**9+7
fact=[1]
fact_r=[1]
for i in range(1,H+W-1):
    fact.append(i*fact[i-1]%mod)
    fact_r.append(pow(fact[i],10**9+5,mod))
const=fact_r[H-A-1]*fact_r[A-1]%mod
ans=sum(fact[H+i-A-1]*fact_r[i]*fact_r[W-i-1]*fact[W-i-2+A]%mod for i in range(B,W))
print(ans*const%mod)

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

def inv(x, p):
    pp = p-2
    ans = 1
    while pp > 0:
        if pp % 2 == 1:
            ans = (ans * x) % p
        x = (x ** 2) % p
        pp //= 2
    return ans

I = [1] + [inv(i, mod) for i in range(1, h+w+1)]

a0 = 1
a1 = 1
for i in range(w-b+a-1, (w-b+a-1)-(w-b-1), -1):
    a1 = (a1 * i) % mod

for i in range(w-b-1+1):
    
    a1 = (a1 * I[i]) % mod

A0 = [a0]
A1 = [a1]
for i in range(1, h-a):
    a0 = (a0 * (b-1+i)) % mod
    a0 = (a0 * I[i]) % mod
    A0.append(a0)

    a1 = (a1 * (w-b+a-1+i)) % mod
    a1 = (a1 * I[(w-b+a-1)-(w-b-1)+i]) % mod
    A1.append(a1)



ans = 0
for i in range(h-a):
    pl = (A0[i] * A1[-i-1]) % mod
    ans = (ans + pl) % mod

print(ans)

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

fac = [1] * (m + 1)
inv = [1] * (m + 1)
for i in range(1, m + 1):
    fac[i] = fac[i - 1] * i % mod
inv[-1] = pow(fac[-1], mod - 2, mod)
for i in range(m - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod


def cmb(n, r):
    assert n >= r >= 0
    ret = fac[n] 
    ret *= inv[n - r]
    ret %= mod
    ret *= inv[r]
    return ret % mod


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

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

fac = [1] * (m + 1)
inv = [1] * (m + 1)
for i in range(1, m + 1):
    fac[i] = fac[i - 1] * i % mod
inv[-1] = pow(fac[-1], mod - 2, mod)
for i in range(m - 1, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod


def cmb(n, r):
    assert n >= r >= 0
    return fac[n] * inv[n - r] * inv[r] % mod


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