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



Sample input:
2 3 1 1


Sample output:
2

Submission status: Accepted

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


class Combination:
    """
  O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
  n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
  使用例：
  comb = Combination(1000000)
  print(comb(5, 3))  # 10
  """

    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):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        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):
        # 0からnまでのmod逆元のリストを返す O(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

comb = Combination(1000000)
MOD = 10**9+7
ans = 0
for i in range(B,W):
    ans += comb(H-A-1+i,i)*comb(A-1+W-1-i,A-1)
    ans %= MOD
    #print(comb(H-A-1+i,i)*comb(A-1+W-1-i,A-1))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

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


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

    cmb = Combination(H+W+1, MOD)

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

    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))  # type: int
    W = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(H, W, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007

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

def f(n):
  return fac[B+n+H-A-1] * fac[W-B-1-n+A-1] * ifac[B+n] * ifac[H-A-1] * ifac[W-B-1-n] * ifac[A-1]

def sigma(func, frm, to):
  result = 0
  for i in range(frm, to+1):
    result += func(i)
  return result
 
print(sigma(f, 0, W-B-1)%MOD)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
MAX_NUM = 2*10**5 + 1
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=0
while 1:
    a=(a+c(H-A-1+B,B)*c(A+W-B-1,A))%pr
    A+=1
    B+=1
    if A==H or B==W:
        break
print(a)

Submission status: Accepted

Solution code:
from operator  import mul
from functools import reduce

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6
fact    = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv     = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#kari1 = '2 3 1 1'                   #2
#kari1 = '10 7 3 4'                  #3570
#kari1 = '100000 100000 99999 99999' #1
#kari1 = '100000 100000 44444 55555' #738162020

"""
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0])
W = int(in1[1])
A = int(in1[2])
B = int(in1[3])

allCNT = 0
for idx1 in range(W - B):
    beforeCNT = cmb(H - A + B - 1 + idx1, H - A - 1, p)
    afterCNT  = cmb(W + A - B - 2 - idx1, A - 1, p)
    allCNT    = (allCNT + (beforeCNT * afterCNT) % p) % p

print(allCNT)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 2 * 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

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

Submission status: Accepted

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

MOD = 1000000007


def modPow(a, x, p):
    res = 1
    while (x > 0):
        if (x % 2 != 0):
            res = (res * a) % p
        a = (a * a) % p
        x /= 2
    return res


fact = [None] * 220000

for i in range(1, 220000):
    fact[0] = 1
    fact[i] = i * fact[i - 1] % MOD
    # inv[i] = modPow(fact[i], MOD-2, MOD)


def ncr(n, r):
    den = fact[n - r] * fact[r] % MOD
    return fact[n] * pow(den, MOD - 2, MOD) % MOD


def number_of_paths(h, w):
    n = h + w - 2
    r = h - 1
    return ncr(n, r)


ans = 0
for i in range(b + 1, w + 1):
    # print('first', h-a, i)
    ans += number_of_paths(h - a, i) * number_of_paths(a, w - i + 1)

print(int(ans % MOD))

Submission status: Accepted

Solution code:
h,w,a,b = map(int, input().split())
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
def find_inv_power(n):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist
mod = 10**9+7
p_lis=find_power(4*10**5+100,mod)
ip_lis=find_inv_power(4*10**5+100)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
        
        
    ans=cmb(N-2,H-1,mod)
    
    for i in range(min(A,B)):
        h=H-A+i+1
        w=B-i
        #print(h,w,cmb(h+w-2,h-1,mod),cmb(H+W-(h+w),H-h,mod))
        ans-=cmb(h+w-2,h-1,mod)*cmb(H+W-(h+w),H-h,mod)
        ans%=mod
        
    print(ans%mod)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


class Cmber:
    def __init__(self,gensize,mod=10**9+7):
        self.mod = mod
        self.g1=[1,1]
        self.g2 = [1, 1] #逆元テーブル
        self.inverse = [0, 1] #逆元テーブル計算用テーブル
        self.getgen(gensize)
    def getgen(self,N):
        for i in range( 2, N + 1 ):
            self.g1.append( ( self.g1[-1] * i ) % self.mod )
            self.inverse.append( ( -self.inverse[self.mod % i] * (self.mod//i) ) % self.mod )
            self.g2.append( (self.g2[-1] * self.inverse[-1]) % self.mod )

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

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


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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
mod=10**9+7
ans=0
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = h+w+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

#a = cmb(n,r,mod)
for i in range(h-a):
    p=(i)+(b-1)
    q=(h-i-1)+((w-b)-1)
    ans+=cmb(p,i,mod)*cmb(q,h-i-1,mod)
    ans%=mod
    #print(p,q)
print(ans)

Submission status: Accepted

Solution code:
import math

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

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

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

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

ans = 0
for j in range(h-a):
    tmp = comb(b-1+j,j)*comb(w+h-b-2-j,w-b-1)%mod
    ans += tmp
    ans = ans%mod
#    ans = ans + fact[b-1+j]*fact[w+h-b-2-j]/fact[b-1]/fact[j]/fact[w-b-1]/fact[h-1-j]
print(int(ans))

'''
単純なh*wのマス目だった場合
#h-row / w-col
con = [[0]*w]*h
for i in range(h):
    con[i][0] = 1
for j in range(w):
    con[0][j] = 1

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

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

'''
全量を計算するやり方
H*Wがデカすぎると時間というよりもメモリエラー
print('initialize')
con = [[0 for i in range(w)] for j in range(h)]
#リスト内包表記で作らないとバグる
#ダメな例 -> con = [[0]*w]*h
#https://qiita.com/utgwkk/items/5ad2527f19150ae33322
print('initialize finished')


for i in range(h-a):
    con[i][0] = 1
#print(con[0])
for j in range(w):
    #wは先に初期化やっちゃう
    con[0][j] = 1
#print(con)

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

for m in range(1,h):
#    print('---{} row---'.format(m))
#    print(con[m])
    for n in range(b,w):
#        print('m,n:('+str(m)+','+str(n)+')')
        con[m][n] = con[m-1][n] + con[m][n-1]
#    print(con[m])

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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


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

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


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


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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

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

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

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

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

def nCk(n, k, MOD):
    # log("{}C{} = {}".format(n,k,nPk(n,k, MOD) * inv(kaijo[k], MOD)))
    return nPk(n,k, MOD) * inv(kaijo[k], MOD)

h, w, a, b = get_nums_l()

ans = 0
for i in range(h-a):
    # (0,0)から(b-1, i)に到着するパターン数 * (b,i)から(W-1, H-1)に到着するパターン数
    # log(nCk(b+i-1, i, MOD), nCk(w-b+h-i-2, h-i-1, MOD))
    ans += nCk(b+i-1, i, MOD) * nCk(w-b+h-i-2, h-i-1, MOD) % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
# D - いろはちゃんとマス目
def cmb1(n,r,mod):
    if (r<0 or r>n):
        return 0
    r = min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

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

# 前処理
mod=10**9+7 #出力の制限
n=10**6
g1=[1,1] # 元テーブル
g2=[1,1] # 逆元テーブル
inverse=[0,1] #逆元テーブル計算用テーブル

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

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

Submission status: Accepted

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

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

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Submission status: Accepted

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

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % MOD
                inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
                finv[i] = finv[i - 1] * inv[i] % MOD

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
class Combination():
    # コンストラクタ
    def __init__(self, N:int, P:int):
        self.N = N
        self.P = P

        # fact[i] = (i! mod P)
        self.fact = [1, 1]   
        # factinv[i] = ((i!)^(-1) mod P)
        self.factinv = [1, 1]
        # factinv 計算用
        self.inv = [0, 1]    

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

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

    COMB = Combination(H+W, MOD)

    # (1,1) -> (i,B-1) -> (i,B+1) -> (H,W)

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

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

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

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)

Submission status: Accepted

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

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

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

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


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

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

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

    print(ans)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

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

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

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


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

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

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

    print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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

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


row = []
for i in range(h-a):
    row.append(nck(b+i, i))

ans = 0
for i in range(len(row)-1):
    ans += row[i] * nck(w-b-2 + h-1-i, h-1-i)
    ans %= m

ans += row[-1] * nck(w-b-1 + a, a)
ans %= m

print(ans)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import copy

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

ans = 0
for h in range(H-A):
  x = comb(B-1+h, h) # 右にB-1回、下にh回移動する方法の数
  y = comb(W+H-B-h-2, H-h-1) # 右にW-B-1回、下にH-h-1回移動する方法の数
  ans += x*y
  ans %= mod
print(ans)

Submission status: Accepted

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

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

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