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:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007



def main():
	h, w, a, b = LI()

	def comb(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 ** 5 * 2
	fact = [1, 1]
	factinv = [1, 1]
	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)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
factorials=[]
inverses=[]
MOD=10**9+7
factorials.append(1)
curr=1
for i in range(1,h+w+1):
  curr=(curr*i)%MOD
  factorials.append(curr)
for i in range(h+w+1):
  inverses.append(pow(factorials[i],MOD-2,MOD))
ans=0
for i in range(h-a):
  ans=(ans+factorials[b-1+i]*factorials[h-2-i+w-b]*inverses[i]*inverses[b-1]*inverses[h-1-i]*inverses[w-b-1])%MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
fact = [1]
inv = [1]
for i in range(200000):
  fact.append(fact[i] * (i + 1) % mod)
  inv.append(pow(fact[i + 1], mod - 2, mod))
def ncr(n, r):
  if n < 0 or r < 0 or n - r < 0:
    return 0
  return fact[n] * inv[r] * inv[n - r] % mod
h, w, a, b = map(int, input().split())
ans = ncr(h + w - 2, h - 1)
for i in range(min(a, b)):
  ans -= ncr(h - a + b - 1, h - a + i) * ncr(w - b + a - 1, w - b + i)
print(ans % mod)

Submission status: Accepted

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

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, 200000 + 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 k in range(1,h-a+1):
  tmp=cmb(k-1+b-1,k-1,mod)
  tmp*=cmb(h-k+w-b-1,h-k,mod)
  ans+=tmp
  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
size = 2*10**5
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

print(ans)

Submission status: Accepted

Solution code:
def ext_euclid(a, b):
    # return (x, y, gcd(a, b)) such that a * x + b * y = gcd(a, b)
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euclid(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euclid(a, mod)
    return x % mod


def comb_list_1(H, W, A, B, mod, modinv_list):
    # (h+B-1)_C_(B-1)  (h in {0, ..., H-A-1})
    ret = [0 for _ in range(H - A)]
    c = 1
    for h in range(H - A):
        ret[h] = c
        c *= h + B
        c *= modinv_list[h + 1]
        c %= mod
    return ret


def comb_list_2(H, W, A, B, mod, modinv_list):
    # (-h+H+W-B-2)_C_(W-B-1)  (h in {0, ..., H-A-1})
    ret = [0 for _ in range(H - A)]
    # initial value -> (A+W-B-1)_C_(W-B-1)  (h = H-A-1)
    c = 1
    for a in range(1, A + 1):
        c *= (a + W - B - 1)
        c *= modinv_list[a]
        c %= mod
    # fill elements of result list from the back
    for h in range(H - A - 1, -1, -1):
        ret[h] = c
        c *= H - h + W - B - 1
        c *= modinv_list[H - h]
        c %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    H, W, A, B = list(map(int, input().split(' ')))
    modinv_list = [None] + [mod_inv(h, MOD) for h in range(1, H + 1)]  # modinv doesn't exist on h = 0
    combs_1 = comb_list_1(H, W, A, B, MOD, modinv_list)
    combs_2 = comb_list_2(H, W, A, B, MOD, modinv_list)
    ans = 0
    for c1, c2 in zip(combs_1, combs_2):
        ans += c1 * c2
        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
n = h + w

f = [1 for _ in range(n)]
f_inv = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)


def comb(n, k):
    return (f[n] * f_inv[k] % mod) * f_inv[n-k] % mod

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

print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,a,b = map(int,ipt().split())
    mod = 10**9+7

    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 2*10**5
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    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
    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 = cmb(h+w-2,h-1,mod)
    for i in range(max(a,b)):
        ans = (ans-cmb(b+h-a-1,b-1-i,mod)*cmb(a+w-b-1,a-1-i,mod)%mod)%mod
    print(ans)



    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(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

H, W, A, B = map(int, input().split())
ans = 0
n = H + W - B - 1
for i in range(1, H-A+1):
  ans += comb(n-i, H-i) * comb(B+i-2, B-1) % MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# 練習
import math
h,w,a,b = list(map(int, input().split()))
p = 10**9+7
# 方針
# (0,0)    ~ (0,w-1)
# (h-1,0 )~ (h-1,w-1)で考える
# 通れないのは(h-a) ~ (h-1)行かつ(0) ~ (b-1) 列のところ
# b <= i <= w-1 のiについて1,2,3の組み合わせはそれぞれ以下の通り 
# 1, (0,0) ~ (h-a-1,i)      (h-a-1+i)! /(h-a-1)! * i!
# 2, (h-a-1,i )~(h-a,i)　  1
# 3, (h-a,i) ~ (h-1,w-1)   (a-1+w-1-i)! /(a-1)! * (w-1-i)!
def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

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

fac, ifac = make_tables(p, h+w-2)
total = 0
for i in range(b, w):
    r1 = cmb(h-a-1+i,i,p,fac, ifac)
    r3 = cmb(a-1+w-1-i, a-1,p,fac, ifac)
    
    total = total +( r1*r3)
print(total%p)

Submission status: Accepted

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
for i in range(B,W):
  answer+=comb_mod(H-A-1+i,i)*comb_mod(A-1+W-1-i,W-1-i)
  answer%=MOD
    
print(answer)

Submission status: Accepted

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  if 0<=r<=n:
    return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]
  else:
    return 0

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
for i in range(B,W):
  answer+=comb_mod(H-A+B-1,i)*comb_mod(W+A-B-1,W-1-i)
  answer%=MOD
    
print(answer)

Submission status: Accepted

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

def invmod(a):
  return pow(a,MOD-2,MOD)
def comb_mod(n,r):
  return fact_dic[n]*fact_inv_dic[r]*fact_inv_dic[n-r]

fact_dic={0:1}
fact_inv_dic={0:1}
fact_mod=1
for i in range(1,H+W-1):
  fact_mod=(fact_mod*i)%MOD
  fact_dic[i]=fact_mod
  fact_inv_dic[i]=invmod(fact_mod)
  
answer=0
if H-A>=W-B:
  for i in range(B,W):
    answer+=comb_mod(H-A+B-1,i)*comb_mod(W+A-B-1,W-1-i)
    answer%=MOD
else:
  for j in range(H-A):
    answer+=comb_mod(H-A+B-1,B+j)*comb_mod(W+A-B-1,W-B-1-j)
    answer%=MOD
    
print(answer)

Submission status: Accepted

Solution code:
import math
p=1000000007
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,2*(10**5)+1):
    g1.append((g1[-1]*i)%p)
    inverse.append((-inverse[p%i]*(p//i))%p)
    g2.append((g2[-1]*inverse[-1])%p)
def cmb2(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
def chwp(h,w,p):
    if h==1 or w==1:return 1
    else:return cmb2(h+w-2,h-1,p)
h,w,a,b= map(int,input().split())
ans=0
for i in range(1,h-a+1):ans=(ans+chwp(i,b,p)*chwp(h-i+1,w-b,p))%p
print(ans)

Submission status: Accepted

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

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,h+w+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

ans = 0

for i in range(100000):
    x = h-a-i
    y = b+1+i
    
    if 0 >= x or y > w:
        break
    
    ans += nCr(h+w-x-y,h-x,mod)*nCr(x+y-2,x-1,mod)%mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W,A,B = map(int,input().split())
    MAXN = H + W + 3
    factorial = [1]
    for i in range(1,MAXN + 1):
        factorial.append(factorial[-1]*i%MOD)
    inv_factorial = [-1] * (MAXN + 1)
    inv_factorial[-1] = pow(factorial[-1],MOD - 2,MOD)
    for i in range(MAXN - 1,-1,-1):
        inv_factorial[i] = inv_factorial[i + 1]*(i + 1)%MOD
    
    fact = lambda N:factorial[N]
    nck = lambda N,K: 0 if K > N or K < 0 else factorial[N]*inv_factorial[N - K]*inv_factorial[K]%MOD
    dist = lambda sy,sx,gy,gx: nck(gy - sy + gx - sx,gy - sy)
    ans = 0
    if H - A < W - B:
        H,W = W,H
        A,B = B,A
    
    for i in range(W - B):
        x = B + i + 1
        y = H - A - i
        ans += dist(1,1,y,x)*dist(y,x,H,W)%MOD
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def combi_mod(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


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

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans = (not_ans + n) % mod
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans = (ans + n) % mod
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,A,B=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(H+W,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or 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-2+W-i,A-1)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W,A,B = map(int,input().split())
N=H+W
fact = [0]*(N+1)
ifact = [0]*(N+1)
inv = [0]*(N+1)
p=10**9+7

def combination(n):
    fact[0] = 1
    fact[1] = 1
    ifact[0] = 1
    ifact[1] = 1
    inv[1] = 1
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%p
        inv[i] = p - inv[p%i]*(p//i)%p
        ifact[i] = (ifact[i-1]*inv[i])%p
def op(n,k):
    if k<0 or k>n or n<0:
        return 0
    return (fact[n]*ifact[k]*ifact[n-k])%p
combination(N)

b = op(H-A+B-1, B)
res = 0
for i in range(A):
    res = (res + op(W-B-2+i, i))%p
res = (res*b)%p
for i in range(H-A):
    res = (res + op(B+i, i)*op(H-i-1+W-B-2,W-B-2))%p
if H-A==1 and W-B==1:
    res = 1
elif H-A==1:
    res = op(W-B+H-2, H-1)
elif W-B==1:
    res = op(H-A+W-2, W-1)
print(res)

Submission status: Accepted

Solution code:
h,w,a,b = map(int, input().split())
import math
ans = 0
mod = 10**9+7
l =[i for i in range(1,h+w+2)]
for i in range(1,len(l)-1):
    l[i+1] = l[i+1]*l[i]%mod
l = [1]+ l
gyakugen = [pow(l[i], mod-2, mod) for i in range(1, len(l))]
gyakugen = [1] + gyakugen
for p in range(1, w-b+1):
    ans += l[(h-a-1+b+p-1)]*l[w-(b+p)+a-1]*\
    gyakugen[h-a-1]*gyakugen[b+p-1] * gyakugen[a-1]*gyakugen[w-(b+p)]
print(int(ans)%mod)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
mod = int(1e9) + 7
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod
fact = [1 for _ in range(H+W+A+B+1)]
invf = [1 for _ in range(H+W+A+B+1)]
for i in range(H+W+A+B):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[-1] = inved(fact[-1])
for i in range(H+W+A+B, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
S = 0
for i in range(H-A):
  S += (fact[i+B-1] * invf[i] * fact[H-i+W-B-2] * invf[H-1-i]) % mod
  S %= mod
S *= (invf[B-1] * invf[W-B-1]) % mod
S %= mod

print(S)

Submission status: Accepted

Solution code:
# Combination
MOD = 10**9+7
MAX = 2*10**5
fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

H, W, A, B = map(int, input().split())
ans = 0
for i in range(1, H-A+1):
    cnt = comb(i-1+B-1, i-1)
    #print(i, cnt)
    cnt *= comb(H-i+W-B-1, H-i)
    ans += cnt
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#ライブラリの点検
class Data():
    def __init__(self):
        self.power=1
        self.rev=1     
class Combi():
    def __init__(self,N,mod):
        self.lists=[Data() for _ in range(N+1)]
        self.mod=mod  
        for i in range(2,N+1):
            self.lists[i].power=((self.lists[i-1].power)*i)%self.mod
        self.lists[N].rev=pow(self.lists[N].power,self.mod-2,self.mod)
        for j in range(N,0,-1):
            self.lists[j-1].rev=((self.lists[j].rev)*j)%self.mod

    def combi(self,K,R):
        if K<R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev))%self.mod

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def make_factorial_table(size, mod):
        '''
        fact_mod[i] は i! % mod を表す。fact_mod[0] ~ facto_mod[size] まで計算可能なテーブルを返す
        >>> make_factorial_table(20, 10**9+7)
        [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063]
        '''
        fact_mod = [1] * (size + 1)
        for i in range(1, size + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % mod
        return fact_mod

    def combination(n, r, mod, fact_table):
        '''
        フェルマーの小定理 
        a ^ p-1 ≡ 1 (mod p)
        a ^ p-2 ≡ 1/a (mod p) (逆元)
        nCr = (n!) / ((n-r)! * r!) だが、mod p の世界ではこの分母を逆元を用いて計算しておくことが可能
        
        >>> m = 1000000007
        >>> fact_table = make_factorial_table(100, m)
        >>> combination(10, 5, m, fact_table)
        252
        >>> combination(100, 50, m, fact_table)
        538992043
        '''
        numerator = fact_table[n]
        denominator = (fact_table[n-r] * fact_table[r]) % mod
        # pow はすでに繰り返し二乗法で効率的に実装されている
        return (numerator * pow(denominator, mod-2, mod)) % mod

    h, w, a, b = mi()
    # sigma {k = b to w-1} h-1-a+kCh-1-a * a-1+w-1-kCa-1
    # sample 2 だと {k=4to6} 6+kC6 * 2+6-kC2 = (10C6 * 4C2 + 11C6 * 3C2 + 12C6 * 2C2)
    fact_table = make_factorial_table(2 * h + 2 * w, mod)
    ans = 0
    for k in range(b, w):
        # print(f"{h-1-a+k} {h-1-a} / {a-1+w-1-k} {a-1}")
        ans = (ans + combination(h-1-a+k, h-1-a, mod, fact_table) * combination(a-1+w-1-k, a-1, mod, fact_table)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

lim = 2*10**6
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

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

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

H, W, A, B = MAP()

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

print(ans)

Submission status: Accepted

Solution code:
def combmod_pre(N, p):
    '''
    sample usage:
        p = 10**9+7
        N = 10**6
        fact, finv = combmod_pre(N, p)
        combmod(n, r, p)
    '''
    fact = [1, 1]
    finv = [1, 1]
    inv = [0, 1]
    for i in range(2, N+1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        finv.append((finv[-1] * inv[-1]) % p)
    return (fact, finv)


def combmod(n, r, fact, finv, p):
    '''
    sample usage:
        combmod(3000, 1000, fact, finv, p)
            p is a same value of combmod_pre's argument
            fact, finv is return value of combmod_pre
    '''
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % p


p = 10**9+7
N = 10**6
fact, finv = combmod_pre(N, p)

h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    x = combmod(h - a - 1 + j, j, fact, finv, p)
    y = combmod(a + w - 2 - j, w-1 - j, fact, finv, p)
    ans += x * y
print(ans % p)

Submission status: Accepted

Solution code:
def combmod(n, r, p):
    if r < 0 or n < r:
        return 0
    return fact[n] * finv[r] * finv[n-r] % p


p = 10**9+7
N = 10**6
fact = [1, 1]
finv = [1, 1]
inv = [0, 1]

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

h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    ans += combmod(h-a-1 + j, j, p) * combmod(a+w-2 - j, w-1 - j, p)
print(ans % p)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

n = h+w
fac = [1]*(n+1)
fac_inv =  [0]*(n+1)

for i in range(n):
    fac[i+1] = (fac[i] * (i+1)) %MOD
fac_inv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(n,0,-1):
    fac_inv[i-1] = (fac_inv[i] * i) % MOD
    
def comb(n,k):
    if k<0 or k>n:
        return 0
    x = (fac[n] * (fac_inv[k] * fac_inv[n-k])%MOD)%MOD
    return x

ans = 0

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

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