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

N = 10**6     #出力の制限
mod = 10**9+7 
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 path(a,b):
  h=b[0]-a[0]
  w=b[1]-a[1]
  return cmb(h+w,h,mod)
st,gl = [0,0],[H-1,W-1]
ans = path(st,gl)
for i in range(A):
  ans-=(path(st,[H-i-1,B-1])*path([H-i-1,B],gl))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7
fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def modcmb(n, r, mod):
    if n < 0 or r < 0 or r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


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

    n = 2*10**5+10
    for i in range(2,n):
        fac.append((fac[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD//i)) % MOD)
        f_inv.append((f_inv[-1] * inv[-1]) % MOD)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


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


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
if a >= h // 2:
    ans = 0
    for i in range(1, h - a + 1):
        ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
        if ans >= MOD:
            ans -= MOD
    print(ans)

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

Submission status: Accepted

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

i = H - A - 1
j = B


# 階乗とその逆元を事前計算する (O(N))
# finv[0] := 0の階乗の逆元
def factorial_and_inv(n, mod=10 ** 9 + 7):
    f = [1]
    for n in range(1, n):
        f.append(f[n - 1] * n % mod)
    finv = [0] * n
    finv[n - 1] = pow(f[n - 1], mod - 2, mod)
    for n in range(n - 2, -1, -1):
        finv[n] = finv[n + 1] * (n + 1) % mod
    return f, finv


f, finv = factorial_and_inv(W + H + 2, MOD)
ans = 0
while i >= 0 and W > j:
    path1 = f[i + j] * finv[i] % MOD * finv[j] % MOD
    path2 = f[(H - i - 1) + (W - j - 1)] * finv[H - i - 1] % MOD * finv[W - j - 1] % MOD
    ans += path1 * path2 % MOD
    i -= 1
    j += 1
print(ans % MOD)

Submission status: Accepted

Solution code:

#modの掛け算
 
def modmal(a,b,mod): #a*bをmodを法にして求める
 
    return a * b % mod
 
 
#modの割り算
 
def moddiv(a,b,mod): #a/bをmodを法にして求める
 
    return (a * pow(b,mod-2)) % mod
 
 
#逆元
 
def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2)
 
 
 
#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている
 
def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs
 
 
def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし
 
    return fac[n] * inv[n-r] * inv[r] % mod


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

mod = 10 ** 9 + 7
ans = 0

fac,inv = modfac(H+W,mod)

for i in range(H-A):

    now = modnCr(i + B-1, i,mod,fac,inv)
    now *= modnCr(H+W-i-B-2,W-B-1,mod,fac,inv)

    ans += now
    ans %= mod

print (ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
h,w,a,b=map(int,input().split())
MOD=10**9+7
fac=[0]*2*10**5
finv=[0]*2*10**5
inv=[0]*2*10**5
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,2*10**5):
    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
ans=0
for i in range(b,w):   
    ans+=COM(h-a-1+i,i)*COM(a-1+w-i-1,w-i-1)
    ans=ans%MOD
print(ans)

Submission status: Accepted

Solution code:
class Combination():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
            self.inv[i+1] = self.inv[i]*pow(i+1,mod-2,mod)%mod
    def comb(self,m,k):
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod
        
MOD = 10**9+7
H,W,A,B = map(int,input().split())

cb = Combination(H+W,MOD)

ans = 0

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

Submission status: Accepted

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

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

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

print(answer)

Submission status: Accepted

Solution code:
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def pow(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return pow(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * pow(n, r-1, mod) % mod

def com(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
h,w,a,b=map(int,input().split())
ans=ModInt(0)
mod=10**9+7
k=h-a
com1=[ModInt(0) for i in range(w-b)]
com2=[ModInt(0) for i in range(w-b)]
com1[0]=ModInt(com(k+b-1,b,mod))
com2[0]=com(a-1,0,mod)
for i in range(1,w-b):
    com1[i]=com1[i-1]*ModInt(k+b+i-1)/ModInt(b+i)
    com2[i]=com2[i-1]*ModInt(a+i-1)/ModInt(i)
# print(com1)
com2.reverse()
# print(com2)
for i in range(b+1,w+1):
    ans+=com1[i-b-1]*com2[i-b-1]
    # print(com1[i-b-1],com2[i-b-1])
    # print(com(k+i-2,i-1,mod),com(a+w-i-1,w-i,mod))
print(ans)

Submission status: Accepted

Solution code:
def nCr(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


mod = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

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


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

ans = 0

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

print(ans % mod)

Submission status: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, H + W + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

H, W, Y2, X1 = MAP()

Y1 = H - Y2
X2 = W - X1
mt = ModTools(H+W, MOD)
ans = 0
for x in range(1, X2+1):
    # 上の方の通り数
    cnt1 = mt.nCr(Y1+X1+x-2, Y1-1)
    # 下の方の通り数
    cnt2 = mt.nCr(Y2+X2-x-1, Y2-1)
    ans += cnt1 * cnt2
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
fact = [1]
invfact = [1]
mod = 10 ** 9 + 7
h, w, a, b = map(int, input().split())
for i in range(1, h+w+1):
    fact.append((fact[-1] * i) % mod)
    invfact.append(pow(fact[i], mod - 2, mod))

ans = 0
for i in range(b, w):
    ans += (fact[h - a - 1 + i] * invfact[h - a - 1] * invfact[i]) * \
        (fact[a - 2 + w - i] * invfact[a - 1] * invfact[w - i-1])
    ans %= mod
print(ans)

Submission status: Accepted

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

MOD = 1000000007
fac = [1]
inv = [1]
for i in range(1,200010):
	fac.append(fac[i-1]*i%MOD)
	inv.append(pow(fac[i],MOD-2,MOD))

ans = 0

for i in range(b+1,w+1):
	ans += fac[h-a+i-2]*inv[h-a-1]*inv[i-1]*fac[a+w-i-1]*inv[a-1]*inv[w-i]%MOD
	ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
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**6+3
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 j in range(h-a):
  ans=ans+cmb(b+j-1,j,mod)*cmb(w+h-b-j-2,w-b-1,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
mod = int(1e+9 + 7)
p = mod - 2
X, Y = H-A, W-B
L = []
while p != 0:
  L = [p%2] + L[:]
  p //= 2
S = 0
fL = [1]
invfL = []
for i in range(H+W):
  fL.append(((i+1)*fL[i])%mod)
for i in range(H):
  invi = 1
  for j in range(len(L)):
    if L[j] == 1:
      invi *= fL[i]
      invi %= mod
    if j != len(L)-1:
      invi *= invi
      invi %= mod
  invfL.append(invi)
invB = 1
invW = 1
for i in range(len(L)):
  if L[i] == 1:
    invB *= fL[B-1]
    invB %= mod
    invW *= fL[W-B-1]
    invW %= mod
  if i != len(L)-1:
    invB *= invB
    invB %= mod
    invW *= invW
    invW %= mod
for i in range(X):
  S += (fL[i+B-1]*fL[H+Y-i-2]*invfL[i]*invfL[H-i-1])%mod
  S %= mod
print((S*invB*invW)%mod)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
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
    #[x,y]
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
def kumi(h,w,a):
    a[0]=1
    #print(a)
    for i in range(1,h):
        b=a[i-1]*(w+i)%(10**9+7)
        a[i]=b*mod_inv(i,10**9+7)
        #print(a)
    return a
f=[0]*(H-A)
s=[0]*(H)
f=kumi(H-A,B-1,f)
s=kumi(H,W-B-1,s)
"""print(f)
print(s)"""
ans=0
for i in range(H-A):
    ans+=f[i]*s[-i-1]
print(ans%(10**9+7))
"""ans=0
for i in range(H-A):
    #print(cmb(i+B-1,B-1)%(10**9+7),cmb(H-i+W-B-2,W-B-1)%(10**9+7))
    ans+=cmb(i+B-1,B-1)*cmb(H-i+W-B-2,W-B-1)%(10**9+7)
print(ans%(10**9+7))"""

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join(chr(i+97) for i in ls)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
        
show_flg=False
#show_flg=True

ans=0

h,w,a,b=LI()

cm=Comb(3*10**5,mo)

for i in range(w-b):
    show(i,(h-a+b +i-1,h-a-1),(a-1+w-b-1 -i,a-1))
    show(cm.comb(h-a+b +i-1,h-a-1),cm.comb(a-1+w-b-1 -i,a-1))
    ans+=cm.comb(h-a+b +i-1,h-a-1)*cm.comb(a-1+w-b-1 -i,a-1)
    ans%=mo

print(ans)

Submission status: Accepted

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

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

factorials, invs = prepare(H+W+1,MOD)
ans = 0
for b in range(B,W):
  ans += (factorials[H-A-1+b] * invs[H-A-1] % MOD * invs[b] % MOD) * (factorials[A-1+W-b-1] * invs[A-1] % MOD * invs[W-b-1] % MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
def nCr(n, r):
	global fact, inv, MOD
	return (fact[n] * inv[n-r] * inv[r]) % MOD

MOD = 1000000007
MAX = 200001

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

fact = [1 for i in range(MAX)]
inv = [1 for i in range(MAX)]

for i in range(1, MAX):
	fact[i] = (fact[i-1] * i) % MOD
	inv[i] = pow(fact[i], MOD-2, MOD)

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

print(ans)

Submission status: Accepted

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

mod = 10**9 + 7
n = 10**5 * 2 + 1

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

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod 
ans = 0
for i in range(b,w):
  ans = (ans + comb(h-a-1+i,i) * comb(w-i+a-2,a-1)) % mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
mod2 = 998244353
rng = 200001
fctr = [1]
finv = [1]
for i in range(1,rng):
    fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
    finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
    if n<0 or k<0:
        return 0
    else:
        return fctr[n]*finv[n-k]*finv[k]%mod
h,w,a,b = map(int, input().split(' '))
ans = cmb(h+w-2,h-1)
x = h-a+b-1
for i in range(1,min(a,b)+1):
    ans = (ans-(cmb(x,b-i)*cmb(h+w-2-x,w-b+i-1))%mod)%mod
print(ans)

Submission status: Accepted

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

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2,max_num):
    fact[i] = fact[i-1] * i % mod
    ifact[i] = ifact[i-1] * inv(i,mod) % mod

def cmb(x,y):
    return fact[x] * ifact[y] * ifact[x-y] % mod

ans = 0

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

print(ans)

Submission status: Accepted

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

N = h + w

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

mod = 10 ** 9 + 7

factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % mod



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

Submission status: Accepted

Solution code:
from array import *
import time
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = max(h+w-a-1, a+w)


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
f = array('q', f)
ivf = [0] * MAX
ivf = array('q', ivf)
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))

Submission status: Accepted

Solution code:
mod = int(1e9+7)


def exgcd(a, b, arr):
    if b == 0:
        arr.clear()
        arr.append(1)
        arr.append(0)
        return a
    else:
        d = exgcd(b, a % b, arr)
        x = arr[1]
        y = arr[0] - a//b * arr[1]
        arr[0] = x
        arr[1] = y
        return d


def Inv(a):
    arr = []
    exgcd(a, mod, arr)
    return (arr[0] + mod) % mod


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

fac = [1 for i in range(H + W)]
for i in range(1, len(fac)):
    fac[i] = fac[i-1] * i % mod
inv = [1 for i in range(H+W)]
for i in range(0, len(inv)):
    inv[i] = Inv(fac[i])


def Cnm(n, m):
    return fac[n] * inv[n-m] * inv[m] % mod


ans = Cnm(H+W-2, H-1)
for i in range(1, B+1):
    tmp = Cnm(H-A+i-2, i-1) * Cnm(A+W-i-1, W-i) % mod
    ans = (ans - tmp + mod) % 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)
fact[0] = 1
fact[1] = 1
for x in range(2, H + W + 1):
    fact[x] = x * fact[x - 1] % mod

invs = [-1] * (H + W + 1)
invs[H + W] = pow(fact[H + W], mod - 2, mod)
for x in range(H + W - 1, 0, -1):
    invs[x] = invs[x + 1] * (x + 1) % mod


def combination(n, r):
    if n - r < r:
        return combination(n, n - r)
    if r < 0:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n
    return fact[n] * invs[r] * invs[n - r] % mod


ret = 0
for c in range(B, W):
    ret = (ret + combination(H - 1 - A + c, c) * combination(W - 2 + A - c, A - 1)) % mod
print(ret)

# 左下にA*Bの入れない区画
# S->{aa,bb,cc,dd,ee,ff,gg}->G
# S->aはcombination(H - 1 - A + c, c):aの座標(H-1-A,c),通る列番号cを選ぶ
# a->aは1通り
# a->Gはcombination(W - 2 + A - c, A - 1):aの座標(H-A,c),Gの座標(H-1,W-1)この距離からA-1を選ぶ
# S**********
# *         *
# *         *
# *         *
# ****abcdefg
# *   abcdefg
# *   *     *
# *   *     *
# **********G

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(n=10**6, p=10**9+7):
    fac = [None] * (n + 1)
    fac[0] = 1
    ifac = fac.copy()
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % p
    ifac[n] = pow(fac[n], p - 2, p)
    for i in range(n-1, 0, -1):
        ifac[i] = ifac[i+1] * (i + 1) % p
    return fac, ifac
fac, ifac = make_table()
def comb_mod(n, r, mod=10**9+7):
    if r < 0 or r > n:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

h, w, a, b = map(int, sys.stdin.readline().split())

def main():
    total = comb_mod(h+w-2, h-1)

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

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

Submission status: Accepted

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

#前計算　f[i] = i!
f=[1]
for i in range(h+w):
  f.append(f[i]*(i+1)%mod)

#C(n,r,p) = ( n! * r!^(p-2) * (n-r)!^(p-2) )%p
#pythonだとpow()で二分累乗法が使える
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)

Submission status: Accepted

Solution code:
h, w, a, b = map(int, input().split())
###############
# 二項係数テンプレート
# 出力制限
mod = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5
factorial = [1] * MAX_N
#事前に階乗テーブルを用意
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 階乗を用意
calc_factorial()
#########

# 全体の組み合わせを計算する
# h-1(高さ)+w-1(横幅)から、h-1(高さ)個取り出す組み合わせ
all = comb(h + w - 2, h - 1)
sub = 0
for j in range(1, b + 1):
    sub += comb(h - a - 1 + j - 1, j - 1) * comb(a - 1 + w - j, w - j)
    sub = sub % mod
if all - sub <= 0:
    print(all - sub + mod)
else:
    print(all - sub)

Submission status: Accepted

Solution code:
import sys
h, w, a, b = [int(i) for i in sys.stdin.readline().split()]
dic = dict()
MOD = 10**9+7

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

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 )



res = 0
_sum = 0
for i in range(h - a):
    dic[i] = nCr(i + b, i)
    res += (dic[i] - _sum) * nCr(h - i - 1 + w - b - 1, h - i - 1)
    _sum = dic[i]
    res %= MOD
print(res)

Submission status: Accepted

Solution code:

#ABC042D
H, W, A, B = map(int, input().split())
mod=10**9+7
N=H+W+1
bikkuri=[0 for i in range(N)]
bikkuri[0]=1
for i in range(1,N):
    bikkuri[i] = (i * bikkuri[i-1])%mod
gyaku=[0 for i in range(N)]
gyaku[0]=1
for i in range(1, N):
    gyaku[i]=pow(bikkuri[i], mod-2, mod)
def comb(n,r):
    return bikkuri[n]*gyaku[n-r]*gyaku[r]%mod
def homb(n,r):
    return comb(n+r,r)%mod
dame = []
for i in range(B):
    dame.append(homb(H-A-1, i) * homb(W-1-i,A-1))
ans = homb(W-1, H-1) - sum(dame)
print(ans%mod)

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 #出力の制限
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(0,H-A):
  former=cmb(i+B-1,i,mod)
  latter=cmb((H-1-i)+(W-1-B),(H-1-i),mod)
  ans+=(former%mod)*(latter%mod)
  ans%=mod

print(ans)

Submission status: Accepted

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

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

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 )

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

print(ans%mod)

Submission status: Accepted

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

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

def cmb(n,r):
    return fac[n] * inv[r] * inv[n-r] % mod
    
for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans = (ans+e)%mod

print(ans)

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 #出力の制限
n = 3*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

L = []
i = H-A
j = B+1
while i > 0 and j <= W:
    L.append((i, j))
    i -= 1
    j += 1
    
ans = 0
for t in L:
    i = t[0]
    j = t[1]
    ans += (cmb(i+j-2, i-1, mod) * cmb(H-i+W-j, H-i, mod)) % mod
    ans %= mod
    
print(ans)