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:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
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)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
def f(x,y):
    return fact[x-1+h-y]*fact[y-1+w-x]*inv_fact[x-1]*inv_fact[y-1]*inv_fact[w-x]*inv_fact[h-y]%mod
h,w,a,b = LI()
fact = [1]*(h+w+1)
for i in range(h+w):
    fact[i+1] = fact[i]*(i+1)%mod
inv_fact = [0]*(h+w+1)
inv_fact[h+w] = pow(fact[-1],mod-2,mod)
for i in range(h+w)[::-1]:
    inv_fact[i] = inv_fact[i+1]*(i+1)%mod
ans = 0
for i in range(1,min(w-b,h-a)+1):
    ans += f(b+i,a+i)
    ans %= mod
print(ans)

#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
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)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
def f(x,y):
    return fact[x-1+h-y]*fact[y-1+w-x]*inv_fact[x-1]*inv_fact[y-1]*inv_fact[w-x]*inv_fact[h-y]%mod
h,w,a,b = LI()
fact = [1]*(h+w+1)
for i in range(h+w):
    fact[i+1] = fact[i]*(i+1)%mod
inv_fact = [0]*(h+w+1)
inv_fact[h+w] = pow(fact[-1],mod-2,mod)
for i in range(h+w)[::-1]:
    inv_fact[i] = inv_fact[i+1]*(i+1)%mod
ans = 0
for i in range(1,min(w-b,h-a)+1):
    ans += f(b+i,a+i)
    ans %= mod
print(ans)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
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)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
h,w,a,b = LI()
ans = 0
k = 1
inv = [pow(i,mod-2,mod) for i in range(h+w+1)]
x = b+1
y = a+1
for i in range(min(x-1,h-y)):
    k *= (x-1+h-y-i)*inv[i+1]%mod
    k %= mod
for i in range(min(y-1,w-x)):
    k *= (y-1+w-x-i)*inv[i+1]%mod
    k %= mod
for i in range(1,min(w-b,h-a)+1):
    ans += k
    ans %= mod
    k *= (h-y)*(w-x)*inv[x]*inv[y]%mod
    k %= mod
    x += 1
    y += 1
print(ans)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

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

mod = 10**9+7
fact = [1]
for i in range(1, H+W+1):
    fact.append ( fact[-1] * i % mod)

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

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

inv_fact[0] = 1

def C(a,b):
    if a <= 0 or b < 0:
        return 0
    if a==0 or b == 0:
        return 1
    return fact[a] * inv_fact[b] * inv_fact[a-b] % mod

ans = 0
for w in range(B+1, W+1):
    h = H-A - (w-B-1)
    if w == 0 or h == 0:
        break
    ans = (ans + C(h+w-2, w-1) * C(H+W-h-w, W-w) % mod) % mod
print(ans)

Submission status: Accepted

Solution code:
Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv
modfunctional = [1]*(2*10**5+1)
modinv = getInv(10**5+1)
modinvfunctional = [1]*(10**5+1)
for i in range(10**5):
    modinvfunctional[i+1] = (modinvfunctional[i]*modinv[i+1])%Q
for i in range(2*10**5):
    modfunctional[i+1] = (modfunctional[i]*(i+1))%Q
H, W, A, B = map( int, input().split())
ans = 0
for i in range(B+1, W+1):
    ans += (modfunctional[i+H-A-2]*modinvfunctional[i-1]*modinvfunctional[H-A-1]%Q)*(modfunctional[A+W-i-1]*modinvfunctional[A-1]*modinvfunctional[W-i]%Q)%Q
    ans %= Q
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

n=h+w+1
fc,inv=[1]*n,[1]*n
for i in range(1,n):
    fc[i]=i*fc[i-1]%mod
inv[n-1]=pow(fc[n-1],mod-2,mod)
for i in range(n-1,0,-1):
    inv[i-1]=inv[i]*i%mod
f=lambda a,b:fc[a+b]*inv[a]*inv[b]%mod

v=0
for i in range(b,w):
    v+=f(h-a-1,i)*f(a-1,w-i-1)%mod
print(v%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 + 1):
    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

print(ans % mod)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
X = [i for i in range(H + W + 1)]
X[0] = 1
for i in range(2, H + W + 1):
    X[i] = X[i - 1] * i % mod
Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod


def combination(x, y):
    return X[x] * Y[y] * Y[x - y] % mod


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

Submission status: Accepted

Solution code:
H, W, A, B = [int(_) for _ in input().split()]
mod = 10**9 + 7

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

Y = X.copy()
Y[-1] = pow(Y[-1], mod - 2, mod)
for i in range(H + W, 1, -1):
    Y[i - 1] = i * Y[i] % mod


def comb(x, y):
    return X[x] * Y[y] * Y[x - y] % mod


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

# http://arc058.contest.atcoder.jp/data/arc/058/editorial.pdf

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()
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:
H, W, A, B = map(int, input().split())
h = {}
p = 10**9+7
q = p - 2
for x in range(H+W-1):
    if h.get(x-1):
        a = (x * h[x-1][0]) % p
    else:
        a = 1
    b = pow(a,q,p)
    h[x] = (a,b)

def C(n, r):
    return h[n][0] * h[r][1] * h[n-r][1]

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

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
h = {}
p = 10**9+7
q = p - 2
for x in range(H+W-1):
    if h.get(x-1):
        a = (x * h[x-1][0]) % p
    else:
        a = 1
    b = pow(a,q,p)
    h[x] = (a,b)

def C(n, r):
    return h[n][0] * h[r][1] * h[n-r][1]

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

print(ans % p)

Submission status: Accepted

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

n = h+w-2

ans = 0
fac = [1]*(n+1)
inv = [1]*(n+1)

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

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

def func(x, y):
    m = fac[x+y]*inv[x]*inv[y]%mod
    return m

for x in range(b, w):
    ans += func(x, h-a-1)*func(w-1-x, a-1)
    ans %= mod

print(ans)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
answer = 0
mod = 1000000007
factorial = [1]
for n in range(1, H+W):
    factorial.append(factorial[n-1]*n%mod)
def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, y//2) ** 2 % mod
    else:
        a = power(x, y//2) ** 2
        return a * x % mod
inverseFactorial = [0] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in range(H+W-2, -1, -1):
    inverseFactorial[n] = inverseFactorial[n+1] * (n+1) % mod
def combi(n, m):
    return factorial[n] * inverseFactorial[m] *inverseFactorial[n-m]%mod

for i in range(B+1, W+1):
    answer = (answer + combi(H-A-2+i, i-1)*combi(A+W-i-1,W-i)) % mod
print(answer)

Submission status: Accepted

Solution code:
H, W, A, B =  (int(i) for i in input().split())

def power(a, b):
	if b == 0:
		return 0
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007


#階乗の逆元を求める
fac_lim = 300000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007

res = conv(H+W-2, H-1)
for i in range(A):
    res -= conv(H-A+i + B-1, B-1) * conv(A-1-i + W-B-1, W-B-1)
    res = res % 1000000007

print(res)

Submission status: Accepted

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

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * (N+1)
inv = [1] * (N+1)

# 階乗
for i in range(1, N+1):
    fac[i] = i * fac[i - 1] % MOD
 
# 普通の逆元テーブル
for i in range(1, N+1):
    inv[i] = pow(fac[i], MOD-2, MOD)
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

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

Submission status: Accepted

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

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N

# 階乗
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 
# 高速な逆元テーブル　最初にN-1を求めておくことであとはiをかけるだけで残りの逆元が算出できる
inv[N - 1] = pow(fac[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

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

Submission status: Accepted

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

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N

# 階乗
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 
# 逆元
inv[N - 1] = pow(fac[N - 1], MOD - 2, MOD)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

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

Submission status: Accepted

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

mod=10**9+7

n=H+W
INV=[None]*(n+1)#1/aのリストを予め作っておく.
for i in range(1,n+1):
    INV[i]=pow(i,mod-2,mod)

k=H+W-2
n=H-1
Combi1=[None]*(k+1)#Combi[i]=iCnを表す.kは必要な分だけ.
Combi1[n]=1
for i in range(n+1,k+1):
    Combi1[i]=Combi1[i-1]*i*INV[i-n] %mod

k=H+B-2
n=B-1
Combi2=[None]*(k+1)#Combi[i]=iCnを表す.kは必要な分だけ.
Combi2[n]=1
for i in range(n+1,k+1):
    Combi2[i]=Combi2[i-1]*i*INV[i-n] %mod

k=W-B-1+A
n=W-B-1
Combi3=[None]*(k+1)#Combi[i]=iCnを表す.kは必要な分だけ.
Combi3[n]=1
for i in range(n+1,k+1):
    Combi3[i]=Combi3[i-1]*i*INV[i-n] %mod




ANS=Combi1[H+W-2]
for x in range(H-A,H):
    ANS=(ANS-Combi2[x+B-1]*Combi3[(H-x-1)+W-B-1])%mod


print(ANS)

Submission status: Accepted

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

Factorial=[1]*(H+W+1)
for i in range(1,H+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(H+W+1)
inverseFactorial[H+W]=power(Factorial[H+W],mod-2)
for i in range(0,H+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
ans=0
for a in range(0,H-A):
  ans=(ans+comb(B+a-1,a)*comb(W-B+H-a-2,H-a-1))%mod
print(ans)

Submission status: Accepted

Solution code:
K = 10 ** 9 + 7

def pow_K(x, n):
  if n == 0:
    return 1
  else:
    return (pow_K(x, n // 2) ** 2 * x ** (n % 2)) % K

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

fact = [0 for i in range(H+W-1)]
fact[0] = 1
for i in range(H+W-2):
  fact[i + 1] = fact[i] * (i+1) % K
fact_inv = [0 for i in range(H+W-1)]
fact_inv[H+W-2] = pow_K(fact[H+W-2], K-2)
for i in range(H+W-2, 0, -1):
  fact_inv[i-1] = fact_inv[i] * i % K

r = 0
for i in range(B, W):
  r += ((fact[H-A-1+i] * fact_inv[H-A-1] %K)*fact_inv[i] % K) * ((fact[W-1-i+A-1] * fact_inv[W-1-i] %K) * fact_inv[A-1] % K) %K
  r %= K

print(r)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
M = 10 ** 5 + 5
M *= 2
fact = [0] * M
rfact = [0] * M
fact[0] = 1
MOD = 10 ** 9 + 7
for i in range(1, M):
    fact[i] = fact[i - 1] * i % MOD

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


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


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

print(num)

Submission status: Accepted

Solution code:
def mod_inv(inv,a,m):
    i=a
    if inv.get(a,0)!=0:
        return inv[a]
    e=m-2
    tmp=1
    while e!=1:
        if e%2==1:
            tmp*=a
            tmp%=m
        a*=a
        a%=m
        e//=2
    a*=tmp
    a%=m
    inv[i]=a
    return a

def factrial(fact,a,m):
    for i in range(1,a+1):
        fact[i]=fact[i-1]*i%mod

def comb(fact,inv,a,b,m):
    return (fact[a+b]*mod_inv(inv,fact[a],m)*mod_inv(inv,fact[b],m))%m

H,W,A,B=list(map(int,input().split()))
mod=10**9+7
fact=[1 for _ in range(H+W+1)]
inv={}
factrial(fact,H+W,mod)

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

Submission status: Accepted

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

f, invf = [1] * maxf, [1] * maxf

for i in range(1, maxf):
    f[i] = i * f[i - 1] % MOD
invf[maxf - 1] = pow(f[maxf - 1], MOD - 2, MOD)
for i in range(maxf - 1, 0, -1):
    invf[i - 1] = invf[i] * i % MOD

comb = lambda a, b: f[a + b] * invf[a] * invf[b] % MOD

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

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m
N = 10**9+7
R = 10**5*2
modfact = [0]*(R+1)
def modfact_memo(n,N):
    r = 1
    modfact[0] = 1
    for i in range(1,n+1):
        r = r % N * i % N
        modfact[i] = r
modfact_memo(R,N)

# ax ≡ 1 (mod m)
modinv=[0]*(R+1)
def modinv_memo(a,m):
    for i in range(a+1):
        j = modfact[i]
        (inv, q, gcd_val) = egcd(j, m)
        modinv[i] = inv % m
modinv_memo(R,N)

def modconb(n,r,N):
    p = modfact[n]
    q1 = modinv[r]
    q2 = modinv[n-r]
    return p*q1%N*q2%N

H,W,A,B = map(int,input().split())
ans = 0
for r in range(B,W):
    ans += modconb(H-A-1+r,r,N)*modconb(A-1+W-r-1,A-1,N)
    ans %= N

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


class Combination:
    def __init__(self, n, mod):
        assert 0 < n
        self.mod = mod
        self.fact = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for i in range(1, len(self.fact)):
            self.fact[i] = (i * self.fact[i - 1]) % self.mod
            self.inv[i] = pow(self.fact[i], self.mod - 2, self.mod)

    def nCr(self, n, k):
        if n == 0 and k == 0:
            return 1
        assert 0 <= n < len(self.fact) and 0 <= k
        a = self.fact[n]
        b = (self.inv[k] * self.inv[n - k]) % self.mod
        return a * b % self.mod


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

    comb = Combination(100000 * 2 + 10, MOD)

    ans = 0
    for i in range(B + 1, W + 1):
        h, w = H - A - 1, i - 1
        s = comb.nCr(h + w, w) % MOD

        h, w = A - 1, W - i
        t = comb.nCr(h + w, w) % MOD

        ans += (s * t) % MOD
        ans %= MOD
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX = 510000
MOD = 1000000007

fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
        
def 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

def solve():
    ans = 0
    an = H + B - A - 1
    ar = B
    bn = W + A - B - 2
    br = W - B - 1
    for i in range(W-B):
        a = comb(an, ar)
        b = comb(bn, br)
        ans += (a * b) % MOD
        an += 1; ar += 1
        bn -= 1; br -= 1
    return ans % MOD

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

comb_init()
print(solve())

Submission status: Accepted

Solution code:
iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 10**9+7 #法

iLBoxW=iB-1
iLBoxH=iH-iA-1
iRBoxW=iW-iB-1
iRBoxH=iH-1
#iMax = iH+iW-2
iMax = max(iLBoxW+iLBoxH,iRBoxW+iRBoxH)

#nCr = n!/r!(n-r)!

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

#階乗(iDを法とした)の配列
aM = [1]*(iMax+1)
for i in range(1,iMax+1):
    aM[i]=aM[i-1]*i %iD
#各階乗のiDを法とした逆元の配列
aInvM = [1]*(iMax+1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
for i in range(iMax,0,-1):
    aInvM[i-1]=aInvM[i]*i % iD

iRet = 0
for iL in range(0,iLBoxH+1):
    iRet += (aM[iL+iLBoxW]*aInvM[iL]*aInvM[iLBoxW]) % iD * (aM[iRBoxW+iRBoxH-iL]*aInvM[iRBoxW]*aInvM[iRBoxH-iL])%iD
    iRet %= iD
iRet %= iD
print(iRet)

Submission status: Accepted

Solution code:
iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 10**9+7 #法

#初等整数論勉強して解説通りキッチリ実装したった

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

#nCr = n!/r!(n-r)!
#ループ回すだけ版や
def fFr(iX,iR=1):
    if iR == 0 or iX == 0:
        return 1
    else :
        iRet = 1
        for i in range(iR,iX+1):
            iRet *= i
        return iRet

def fnCr(iN,iR):
    if iR == 0:
        return 1
    else:
        return fFr(iN,iR+1) // fFr(iN-iR)

#階乗(iDを法とした)の配列
aM = [1]*(iH+iW-1)
for i in range(1,iH+iW-1):
    aM[i]=aM[i-1]*i %iD
#各階乗のiDを法とした逆元の配列
aInvM = [1]*(iH+iW-1)
aInvM[iH+iW-2] = fBiPow(aM[iH+iW-2],iD-2,iD)
for i in range(iH+iW-2,0,-1):
    aInvM[i-1]=aInvM[i]*i % iD

iRet = 0
for iL in range(0,iH-iA):
    #iRet += (fnCr(iL+iB-1,iL) * fnCr(iW-iB+iH-iL-2,iW-iB-1))%iD
    iRet += (aM[iL+iB-1]*aInvM[iL]*aInvM[iB-1]) % iD * (aM[iW-iB+iH-iL-2]*aInvM[iW-iB-1]*aInvM[iH-iL-1])%iD
    iRet %= iD
iRet %= iD
print(iRet)

Submission status: Accepted

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

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

# 予め組み合わせ計算に必要な階乗と逆元のテーブルを作っておく
factorial = [1] * (H+W)
factorial[0] = 1
factorial[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod

inverse = [1] * (H+W)
# フェルマーの小定理から(x! ** mod-2 % mod == x! ** -1 % mod)
# powに第三引数入れると冪乗のmod付計算を高速にやってくれる
inverse[H+W-1] = pow(factorial[H+W-1], mod-2, mod)
for i in range(H+W-2, 0, -1):
    # 最後から戻っていくこのループならH+W回powするより処理が速い
    inverse[i] = inverse[i+1] * (i+1) % mod

# 組み合わせの数だけ返してくれる関数(自作)
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Submission status: Accepted

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

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

# 予め組み合わせ計算に必要な階乗と逆元のテーブルを作っておく
factorial = [0] * (H+W)
factorial[0] = 1
factorial[1] = 1
inverse = [0] * (H+W)
inverse[0] = 1
inverse[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod
    # フェルマーの小定理から(x! ** mod-2 % mod == x! ** -1 % mod)
    # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
    inverse[i] = pow(factorial[i], mod-2, mod)
    
# 組み合わせの数だけ返してくれる関数(自作)
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

print(ans)

Submission status: Accepted

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

mod=10**9+7
fc,inv=[1]*n,[1]*n
for i in range(1,n):
  fc[i]=i*fc[i-1]%mod
inv[n-1]=pow(fc[n-1],mod-2,mod)
for i in range(n-1,0,-1):
  inv[i-1]=inv[i]*i%mod
f=lambda a,b:fc[a+b]*inv[a]*inv[b]%mod

v=0
for x in range(b,w):
  v+=f(x,h-a-1)*f(w-1-x,a-1)%mod
print(v%mod)

Submission status: Accepted

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

mod = 10**9 + 7
N = H + W - 2

# 階乗
fac = [1] * N
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % mod

# 逆元
inv = [1] * N
inv[N - 1] = pow(fac[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % mod


def f(x, y):
    res = fac[x + y] * inv[x] * inv[y]
    return res % mod


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

Submission status: Accepted

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

mod = 10 ** 9 + 7

# 階乗
fac = [1] * (H + W - 2)
# 逆元
inv = [1] * (H + W - 2)
for i in range(1, H + W - 2):
    fac[i] = (fac[i - 1] * i) % mod
    inv[i] = pow(fac[i], mod - 2, mod)


def f(x, y):
    res = fac[x + y] * inv[x] * inv[y]
    return res % mod


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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,A,B=inpl()
ans = 0

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

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

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

for x1 in range(B+1,W+1):
	y1 = H-A
	x2 = A
	y2 = W-x1+1
	ans += (Comb(x1+y1-2,y1-1)*Comb(x2+y2-2,y2-1))%mod
	ans %= mod

print(ans)

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:
# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod



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

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

# 二項係数の準備
inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)

# 手前×奥を実行して足していく
ans = 0
for h in range(H-A):
    temp = nCr(h+(B-1), h, MOD, fac, facInv) \
            * nCr((H-h-1)+(W-B-1), W-B-1, MOD, fac, facInv)
    ans = (ans + temp) % MOD
    
print(ans)

Submission status: Accepted

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

N = H+W+10
MOD = 10**9+7

fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+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 ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

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