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())
mod = 10**9 + 7

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

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

a0 = 1
a1 = 1
for i in range(w-b+a-1, (w-b+a-1)-(w-b-1), -1):
    a1 = (a1 * i) % mod
# print(a1)
for i in range(w-b-1+1):
    #print("i",i)
    a1 = (a1 * I[i]) % mod

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

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

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

print(ans)

Submission status: Accepted

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

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


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


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

Submission status: Accepted

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

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


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


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

Submission status: Accepted

Solution code:
def solve():
	h,w,a,b = map(int, input().split())
	mx = max(h,w)
	mod = 10**9+7
	fac = [1]*(h+w+1)
	for i in range(1,h+w+1):
		fac[i]=fac[i-1]*i%mod
	inv = [1]*(mx+1)
	inv[-1] = pow(fac[mx], mod-2, mod)
	for i in range(mx-1, -1, -1):
		inv[i] = inv[i+1]*(i+1)%mod
	const = inv[h-a-1]*inv[a-1]%mod
	ans = sum(fac[h-a+i-1]*inv[i]*fac[a+w-2-i]*inv[w-i-1]%mod for i in range(b,w))
	print(ans*const%mod)

if __name__=="__main__":solve()

Submission status: Accepted

Solution code:
def solve():
	h,w,a,b = map(int, input().split())
	mx = max(h,w)
	mod = 10**9+7
	fac = [1]*(h+w+1)
	for i in range(1,h+w+1):
		fac[i]=fac[i-1]*i%mod
	rev = [1]*(mx+1)
	rev[-1] = pow(fac[mx], mod-2, mod)
	for i in range(mx-1, -1, -1):
		rev[i] = rev[i+1]*(i+1)%mod
	const = rev[h-a-1]*rev[a-1]%mod
	ans = sum(fac[h-a+i-1]*rev[i]*fac[a+w-2-i]*rev[w-i-1]%mod for i in range(b,w))
	print(ans*const%mod)

if __name__=="__main__":solve()

Submission status: Accepted

Solution code:
h, w, a, b = map(int, input().split(" "))
div = 10 ** 9 + 7
size = h + w - 1

fact = [0] * size
inverse = [0] * size
inv_calced = [0] * size
fact[:2] = [1, 1]
inverse[:2] = [1, 1]
inv_calced[:2] = [0, 1]

for i in range(2, size):
  fact[i] = fact[i - 1] * i % div
  inv_calced[i] = -inv_calced[div % i] * (div // i) % div
  inverse[i] = inverse[i - 1] * inv_calced[i] % div
  
result = 0
for x in range(b, w):
  y = h - a - 1
  temp_1 = (fact[x+y] * inverse[x] % div) * inverse[y] % div
  temp_2 = (fact[h+w-x-y-3] * inverse[w-x-1] % div) * inverse[h-y-2] % div
  result += ((temp_1 % div) * (temp_2 % div)) % div

print(result % div)

Submission status: Accepted

Solution code:
from math import factorial

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 = [pow(fact[-1], MOD-2, MOD)] # x^(-1) = x^(10^9+5) % (10^9+7), フェルマーの小定理
for i in range(h+w-2, 0, -1): # xが最大の場合を求め、後ろ向きに計算していく
    inv_fact.append(inv_fact[-1] * i % MOD)
inv = list(reversed(inv_fact)) # 逆順に取得

#print(fact, inv_fact, inv)
def comb(x, y):
    return (fact[x] * inv[y] * inv[x-y])

ans = 0
for x in range(b, w):
    ans += ((comb((h-a-1 + x), x)) * (comb((a-1 + w-x-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
 
h,w,a,b=map(int,input().split())
m=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,h+w):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

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

Submission status: Accepted

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

mod = 10**9+7
def nCr(fact, inv, n, r):
    return fact[n] * inv[r] * inv[n-r] % mod

def main():
    H,W,A,B = map(int,input().split())
    fact = [1]
    for i in range(1, H+W+1):
        fact.append(fact[i-1] * i % mod)
    
    inv = [0] * (H+W+1)
    inv[H+W] = pow(fact[H+W], mod-2, mod) # フェルマーの小定理より a**(mod-2)はaの逆元
    for i in range(H+W, 0, -1):
        inv[i-1] = inv[i] * i % mod

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def pow_mod(x, p):
    res = 1
    while p:
        if p % 2:
            res = res * x % MOD
        x = x * x % MOD
        p //= 2
    return res


F = [1]
invF = []


def comb_mod(n, r):
    return F[n] * invF[r] * invF[n - r] % MOD


for i in range(1, H + W - 1):
    F.append(F[-1] * i % MOD)

invF.append(pow_mod(F[-1], (MOD - 2)))
for f in range(len(F) - 1):
    invF.append(invF[-1] * (len(F) - len(invF)) % MOD)
invF = invF[::-1]

res = 0
for i in range(B + 1, W + 1):
    p = H - A - 1
    q = i - 1

    res = (
                  res
                  + comb_mod(H - A - 1 + i - 1, H - A - 1)
                  * comb_mod(A - 1 + W - i, W - i)
          ) % MOD

print(res)

Submission status: Accepted

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

MOD = 10**9 + 7
MAX = h+w + 5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n-k] % MOD

def path(x, y):
    return comb(x+y-2, x-1)

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

Submission status: Accepted

Solution code:
h,w,a,b = map(int,input().split())
n = h+w
mod = 10**9+7
fun = [1]*(n+1)
for i in range(1,n+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n+1)
rev[n] = pow(fun[n],mod-2,mod)
for i in range(n-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
ans = 0
i = h-a
j = b+1
while i > 0 and j <= w:
  ans = (ans+nCr(i+j-2,i-1)*nCr(h+w-i-j,h-i)%mod)%mod
  i -= 1
  j += 1
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)
    # print(n, r)
    return g1[n] * g2[r] * g2[n-r] % mod


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

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


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

Submission status: Accepted

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


# 二分累乗法 で n^x % p を求める
# pow(n,x,p) で得られるので次からはそっちつかう
def power(n, x, p):
    return pow(n,x,p)
    # a = n  # a^(2^0), a^(2^1), ...
    # ans = 1
    # while x > 0:
    #     if x & 1:
    #         ans = (ans * a) % p
    #     x = x >> 1
    #     a = (a ** 2) % p
    # return ans


def solve():
    kaijo = [0] * (H + W + 1)
    kaijo[0] = kaijo[1] = 1
    for i in range(2, H + W + 1):
        kaijo[i] = (i * kaijo[i - 1]) % p
    gyaku = [0] * (H + W + 1)
    gyaku[0] = gyaku[1] = 1
    for i in range(2, H + W + 1):
        gyaku[i] = power(kaijo[i], p - 2, p)

    # for i in range(H + W + 1):
    #     assert (kaijo[i] * gyaku[i]) % p == 1, (kaijo[i], gyaku[i])

    def conb(_x, _y):
        return (kaijo[_x] * gyaku[_y] * gyaku[_x - _y]) % p

    # h = H - A - 1
    # h2 = H - (H - A)
    ans = 0
    for i in range(W - B):
        ans = (ans + conb(H - A - 1 + B + i, H - A - 1) * conb(A - 1 + W - 1 - B - i, A - 1)) % p
    # for i in range(B, W):
    #     tmp1 = kaijo[h + i] * gyaku[h + i] * gyaku[h + i - max(h, i)]
    #     j = W - i - 1
    #     tmp2 = kaijo[h2 + j] * gyaku[h2 + j] * gyaku[h2 + j - max(h2, j)]
    #     ans = (ans + tmp1 * tmp2) % p
    # print(ans)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(n+1)
f_mod_inverse=[1]*(n+1)
for i in range(1,n+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD

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

Submission status: Accepted

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

mod = 10**9 + 7

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

def comb(A,B,mod):
    return f[A] * pow(f[B],mod-2,mod) * pow(f[A-B],mod-2,mod) % mod

res = 0

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

print(res%mod)

Submission status: Accepted

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

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

mod = 10**9+7 #出力の制限
N = maximum = max(H - A + W - 2, W + A - B - 2)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

for i in range(W - B):
    #前半の経路
    P = 10 ** 9 + 7
    prev = cmb(H - A + B - 1 + i, H - A - 1, P) % P
    latter = cmb(A - 1 + W - B - 1 - i, A - 1, P) % P
    ans += (prev * latter) % P
    ans = ans % P
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    v = 1
    fs = [v]
    for i in range(1, H+W-1):
        v = (v * i) % mod
        fs.append(v)

    v = invfactorial(H+W-2, mod)
    invfs = [v]
    for i in range(H+W-2, 0, -1):
        v = (v * i) % mod
        invfs.append(v)
    invfs = invfs[::-1]

    tot = (fs[H+W-2] * invfs[H-1] * invfs[W-1] ) % mod
    subtract = 0
    for b in range(B):
        v1 = (fs[H-1-A+b]*invfs[b]*invfs[H-1-A]) % mod
        v2 = (fs[A-1+W-1-b] * invfs[A-1] * invfs[W-1-b]) % mod
        subtract += v1 * v2
        subtract %= mod
    # print(tot, subtract)
    return (tot - subtract) % mod


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

def invfactorial(x, mod):
    v = 1
    for i in range(1, x+1):
        v = (v * i) % mod
    return powquick(v, mod-2, mod)



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

Submission status: Accepted

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

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

    MOD = int(1e9) + 7

    kai = [1] * (max(H-A+W, A+W-B) + 1)
    for i in range(1, len(kai)):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD
    
    up = [0] * (W-B)
    down = [0] * (W-B)

    t1 = H-A-1
    for i in range(W-B):
        t2 = B + 1 + i-1
        # print(t1, t2)
        up[i] = kai[t1 + t2] * pow(kai[t1], MOD-2, MOD) * pow(kai[t2], MOD-2, MOD)
        up[i] %= MOD
    t1 = A-1
    for i in range(W-B):
        t2 = W-B-i-1
        # print(t1, t2)
        down[i] = kai[t1 + t2] * pow(kai[t1], MOD-2, MOD) * pow(kai[t2], MOD-2, MOD)
        down[i] %= MOD
    
    ans = 0
    for i in range(W-B):
        ans += (up[i] * down[i])
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

U = 2*(10**5)
MOD = 10**9 + 7

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

def comb(n, k) :
    if k < 0 or k > n :
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n-k]
    x %= MOD
    return x

ans = 0
for x in range(B,W) :
    if x == B :
        ans += comb(H-A-1+x, x) * comb(A+W-1-x, W-1-x)
    else :
        ans += (comb(H-A-1+x, x) - comb(H-A-1+x-1, x-1)) * comb(A+W-1-x, W-1-x)
    ans %= 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 = int(10**9+7) #出力の制限
NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

Submission status: Accepted

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

MOD = 10**9 + 7

def mul(a, b):
    return ((a % MOD) * (b % MOD)) % 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

def div(a, b):
    return mul(a, power(b, MOD-2))

# 階乗計算
fac = [1] * N
for i in range(1, N): 
    fac[i] = fac[i-1] * i % MOD
    
invfac = [0] * (N)
invfac[H+W-1] = power(fac[H+W-1], MOD-2)
for i in range(H+W-2, -1, -1):
    invfac[i] = invfac[i+1] * (i+1) % MOD
    
def nCr(n, r):
    return fac[n] * invfac[r] * invfac[n-r] % MOD



ans = 0
f = {}
for i in range(H-A):
    h1 = i
    w1 = B-1
    if (h1, w1) in f:
        zenhan = f[(h1, w1)]
    else:
        zenhan = nCr(h1+w1,h1)
        f[(h1, w1)] = zenhan
    
    h2 = (H-1) - i
    w2 = (W-1) - B
    if (h2, w2) in f:
        kouhan = f[(h2, w2)]
    else:
        kouhan = nCr(h2+w2,h2)
        f[(h2, w2)] = kouhan

    ans += zenhan * kouhan

print(ans % MOD)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from functools import lru_cache


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

lru_cache(maxsize=None)
def cmb(c, r):
    return fc[c + r] * ic[c] * ic[r] % mod
 
fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % mod
ic = [pow(x, mod-2, mod) for x in fc]
 
if H-A <= W-B:
    for i in range(0,H-A):
        ans += cmb(i, B-1) * cmb(H - 1 - i,W - 1 -B ) % mod
else:
    for i in range(B, W):
        ans += cmb(i, H - 1 - A) * cmb(W - 1 - i, A - 1) % mod
  
print(ans%(mod))

Submission status: Accepted

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

U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x
ans=0
mod=10**9+7
for i in range(1,h-a+1):
    ans+=(comb(i+b-2,min(i-1,b-1))*comb(h-i+w-b-1,min(h-i,w-b-1)))%mod
    ans=ans%mod
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7


def get_fact_list(n: int) -> list:
    result_list = [1]
    tmp = 1
    for i in range(n):
        tmp = (tmp * (i + 1)) % MOD
        result_list.append(tmp)

    return result_list


def get_inv_list(n: int, fact_lit: list) -> list:
    result_list = [1]

    for i in range(n):
        result_list.append(pow(fact_lit[i + 1], MOD - 2, MOD))

    return result_list


def comb(n: int, m: int, fact_list: list, inv_list: list) -> int:
    return (fact_list[n] * inv_list[m] * inv_list[n - m]) % MOD


h = H - A
w = W - B
ways = 0
fact = get_fact_list(H + W)
inv = get_inv_list(H + W, fact)

while h > 0 and w > 0:
    h -= 1
    w -= 1
    ways += (comb(H - A + B - 1, h, fact, inv) * comb(W + A - B - 1, w, fact, inv)) % MOD

print(ways % MOD)

Submission status: Accepted

Solution code:
# ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
def get_fact(lim):
    # compute a toble of factorials (1-idx)
    fact = [1] * (lim + 1)
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        fact[i] = x
    return fact


def get_inv(lim):
    # compute a toble of inverse factorials (1-idx)
    inv = [1] * (lim + 1)
    inv[lim] = pow(fact[lim], MOD - 2, MOD)
    x = inv[lim]
    for i in range(lim - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x
    return inv


def comb(n: int, r: int) -> int:
    # compute nCr (n! / r!(n - r)!)
    return fact[n] * inv[n - r] * inv[r]


def main():
    global MOD, fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    fact = get_fact(H + W)
    inv = get_inv(H + W)
    x, y, a = H - A - 1, W + A - 2, A - 1  # fixed variables
    ans = sum(comb(x + i, i) * comb(y - i, a) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC042D - いろはちゃんとマス目 / Iroha and a Grid (ARC058D)
def comb(n: int, r: int) -> int:
    return fact[n] * inv[n - r] * inv[r]


def main():
    global fact, inv
    H, W, A, B = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    # table of factorials
    fact, x = [1] * (H + W + 1), 1
    for i in range(1, H + W + 1):
        x = (x * i) % MOD
        fact[i] = x
    # table of inverse factorials
    inv = [1] * (H + W + 1)
    inv[-1] = pow(fact[-1], MOD - 2, MOD)
    x = inv[-1]
    for i in range(H + W - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W,A,B = map(int,input().split())
MOD = (10**9)+7
D = [0,2, 9, 11, 14, 15, 17, 19, 20, 23, 24, 25, 27, 28, 29]

def inv(a):
    ans = 1
    hoge = a
    for count in range(31):
        if (count) in D:
            ans *= hoge
            ans %= MOD
        hoge *= hoge
        hoge %= MOD
    return ans

g = [1]*(H+W)
for i in range(1,H+W):
    g[i] = (g[i-1]*i%MOD)
ans = 0
for i in range(H-A):
    L = g[B-1+i]*inv(g[B-1])*inv(g[i])
    R = g[(W-B-1)+(H-1-i)]*inv(g[(W-B-1)])*inv(g[H-1-i])
    ans += L*R%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
h,w,a,b=map(int,input().split())
n=h+w
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod % i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod
 
ans=0
while a<h and b<w:
    ans=(ans+cmb(h-1-a+b,b)*cmb(w-1-b+a,a))%mod
    a+=1
    b+=1
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size=100, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, size + 2):
            self.fact[i] = self.fact[i - 1] * i % mod
            self.inv[i] = -self.inv[mod % i] * (mod // i) % mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

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

    comb = Combination(H + W + 100)

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

    print(ans)


sol()

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
MAX = 200000
MOD = 1000000007
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD  
# sum_{i=B}^{W-1} C_{H-A-1+i}_{i}C_{A+W-i-2}_{A-1}
r = 0
for i in range(B, W):
  r += fac[H-A-1+i]*(finv[H-A-1]*finv[i]%MOD)%MOD * fac[A+W-i-2]*(finv[A-1]*finv[W-1-i]%MOD)%MOD
  r = r%MOD
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
high, width, y, x = map(int, input().split())

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

mod = 10**9 + 7
inv = mod - 2
maxn = high + width - 2
fact = [0] * (maxn+1)
finv = [0] * (maxn+1)
fact[0] = fact[1] = 1
finv[0] = finv[1] = 1

# 階乗を求める
for i in range(2, maxn+1):
    fact[i] = (fact[i-1] * i) % mod

# 階乗の逆元を求める
for i in range(2, maxn+1):
    finv[i] = pow(fact[i], inv, mod)

route = 0
for i in range(1, high-y+1):
        route += (nCr(x+i-2, i-1) * nCr(width+high-x-1-i, high-i)) % mod
        route = route % mod
print(int(route))

Submission status: Accepted

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

SIZE = h+w+2
MOD = 10**9 + 7
MOD_Farmer = 10**9+5

fact = [0] * SIZE
inv = [0] * SIZE
fact_inv = [0] * SIZE

# prepare --------------------------------
inv[0] = 0
inv[1] = 1
fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
for i in range( 2, SIZE ):
  inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
  fact[i] = fact[i-1] * i % MOD
  fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
#  fact_inv[i] = fact[i] **( 10**4 ) \
#              * fact[i] **( 10**5 ) \
#              * fact[i] ** 5 % MOD % MOD
# ----------------------------------------
def comb( n, r ):
  if r >= 0 and n >= 0:
    return fact[n] * fact_inv[n-r]%MOD * fact_inv[r]%MOD
  else :
    return 0.0
# ----------------------------------------

#print( fact_inv )

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

Submission status: Accepted

Solution code:
mod=10**9+7
g1=[1,1]
g2=[1,1]
inverse=[0,1]
h,w,a,b=map(int,input().split())
n=h+w
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod % i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

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

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
n_func=[None for _ in [0]*200001]
n_func[0]=1
for i in range(1,200001):
    n_func[i]=(i*n_func[i-1])%(10**9+7)
def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
def nCr(n,r,mod=10**9+7):return inv_n(n_func[n-r]*n_func[r]%mod,mod)*n_func[n]%mod

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

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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

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

def comb(n,r):
    return fact[n] * pow(fact[r],mod-2,mod) * pow(fact[n-r],mod-2,mod) % mod
ans = 0
for i in range(b,w):
    x = comb(h-a-1+i,i)*comb(a-1+w-i-1,a-1) % mod
    ans += x
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
fact=[1]
temp=1
for i in range(1,3*10**5+1):
    temp*=i
    temp%=MOD
    fact+=[temp]

def bino(a,b):
    if a<b:
        return 0
    up=fact[a]
    down=fact[a-b]*fact[b]
    return (up*pow(down,MOD-2,MOD))%MOD

def find(H,W,A,B):
    temp=0
    for x in range(1,H-A+1):
        temp+=bino(x+B-2,x-1)*bino(W-B-1+H-x,H-x)
        temp%=MOD
    return temp

H,W,A,B=list(map(int,input().strip().split(" ")))
print(find(H,W,A,B))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
SIZE=200001; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

h,w,a,b = [int(i) for i in readline().split()]


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

print(ans)

Submission status: Accepted

Solution code:

def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

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

MOD = 10 ** 9 + 7

#O(N)
first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) * modinv(i, MOD)) % MOD
    first.append(tmp)

# print (first)

#O(N)
second = []
for i in range(0, H):
    if i == 0:
        tmp = 1
        second.append(tmp)
        continue
    tmp = (tmp * ((W - B) + i - 1) * modinv(i, MOD)) % MOD
    second.append(tmp)

# print (second)

#O(N)
ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - 1 -i]) % MOD

print (ans)
#total O(3 * N) --> O(N)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
N=H+W
mod=10**9+7
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]
ans=0
for i in range(H-A):
    ans+=Comb(B+i-1,i)*Comb((W-B-1)+(H-i-1), H-i-1)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import math

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

inp = input().split(' ')
inpint = [int(i) for i in inp]
h = inpint[0]
w = inpint[1]
a = inpint[2]
b = inpint[3]

xfac = [0 for r in range(h+w-2)]
xfac_inv = [0 for r in range(h+w-2)]

for i in range(h+w-2):
	if i == 0:
		xfac[i] = 1
	else:
		xfac[i] = (xfac[i-1]*i)%1000000007

for i in reversed(range(h+w-2)):
	if i == h+w-3:
		xfac_inv[i] = modinv(math.factorial(i),1000000007)
	else:
		xfac_inv[i] = xfac_inv[i+1] * (i+1) % 1000000007

# print(xfac)
# print(xfac_inv)

# for i in range(h+w-2):
# 	print(xfac[i]*xfac_inv[i]%1000000007)

def com(a,b):
	return (xfac[a] * xfac_inv[b] * xfac_inv[a-b])%1000000007

sum = 0
for i in range(b,w):
	sum += com(i + h-a-1,h-a-1) * com((a-1)+w-i-1, w-i-1)
	sum %= 1000000007

print(sum)

Submission status: Accepted

Solution code:
def frac_with_mod(a,m):
    outlist = [ 1 for i in range(a+1) ]
    for i in range(1,a+1):
        outlist[i] = (outlist[i-1] * i)% m
    return outlist

frac_list = frac_with_mod(2*10**5,10**9+7)

def comb_with_mod(a,b,m):
    global frac_list
    return ( frac_list[a+b-2] * pow(frac_list[a-1],m-2,m) * pow(frac_list[b-1],m-2,m) ) % m

mod = 10**9+7
h, w, a, b = [ int(v) for v in input().split() ]

c = h - a
d = w - b


if c == 1:
    waypoint_list = [ 1 for i in range(d) ]
else:
    waypoint_list = [ comb_with_mod(b+1+i,c-1,mod) for i in range(d) ]
    s = comb_with_mod(b,c,mod)

    for i in range(d):
        waypoint_list[i] = ( s + waypoint_list[i] ) % mod
        s = waypoint_list[i]
        waypoint_list[i] = ( comb_with_mod(a,d-i,mod) * waypoint_list[i] ) % mod

print(sum(waypoint_list)%mod)