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:
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = x * i % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = x * (i + 1) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD


# e.g. ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  # fixed variables
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD


# e.g. ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  # fixed variables
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD) % MOD
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_factorials(limit: int, MOD: int) -> list:
    """Compute a mod table of factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x
    return factorials


def mod_comb_with_pow(n: int, k: int, MOD: int) -> int:
    """Compute nCr % MOD using pow()."""
    return fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD) % MOD


# e.g. ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact = get_factorials(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  # fixed variables
    f = lambda i: mod_comb_with_pow(x + i, i, MOD) * mod_comb_with_pow(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""


def get_fact_and_inv(limit: int, MOD: int) -> tuple:
    """Compute mod tables of factorials and inverse factorials (1-indexed)."""
    factorials = [0] * (limit + 1)
    factorials[0] = 1
    x = 1
    for i in range(1, limit + 1):
        x = (x * i) % MOD
        factorials[i] = x

    inverse_factorials = [1] * (limit + 1)
    inverse_factorials[-1] = pow(factorials[-1], MOD - 2, MOD)
    x = inverse_factorials[-1]
    for i in range(limit - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inverse_factorials[i] = x
    return factorials, inverse_factorials


def mod_comb(n: int, r: int, MOD: int) -> int:
    """Compute nCr % MOD using a mod table of inverse factorials."""
    return fact[n] * inv[r] * inv[n - r] % MOD


# e.g. ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
def main():
    global fact, inv
    H, W, A, B = map(int, input().split())
    MOD = 10 ** 9 + 7
    fact, inv = get_fact_and_inv(H + W, MOD)
    x, y, a = H - A - 1, W + A - 2, A - 1  # fixed variables
    f = lambda i: mod_comb(x + i, i, MOD) * mod_comb(y - i, a, MOD)
    ans = sum(f(i) for i in range(B, W)) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
P = 10**9+7
fa = [1]
for i in range(1, 202020):
    fa.append(fa[-1] * i % P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, 202020)[::-1]:
    fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

calc = lambda a, b: fa[a+b] * fainv[a] * fainv[b] % P

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

print(ans)

Submission status: Accepted

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

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

mod = 10**9+7 #出力の制限
N = (10**5)*2+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 )
    
    
w=[]
for i in range(W):
    w.append(cmb(H-A-1+i,i,mod))
#print(w)
w=w[B:]
#print(w)
ans=[]
for i in range(len(w)):
    ans.append(cmb(A-1+(W-B-1-i),W-B-1-i,mod)*w[i])
#print(ans)
print(sum(ans)%mod)

Submission status: Accepted

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

    # comb init
    nmax = 2 * 10 ** 5 + 1  # change here
    fac = [0] * (nmax + 1)
    finv = [0] * (nmax + 1)
    inv = [0] * (nmax + 1)
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        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
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

    p = (comb(b+(h-a-1), b) * comb((w-b-1)+(a-1), a-1)) % mod
    ans = p
    for x in range(b+1, w):
        p = (((p * (x + (h-a-1)))%mod) * ((inv[x] * inv[(w-x)+(a-1)])%mod) * (w-x)) % mod
        ans = (ans + p) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ex = [1]
for i in range(1,2*10**5+1):
    ex.append((ex[-1]*i)%mod)

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

print(ans)

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 getlist():
	return list(map(int, input().split()))
H, W, A, B = getlist()
H -= 1
W -= 1
N = H + W + 2

const = 10 ** 9 + 7
fac = [0] * (N + 1)
inv = [0] * (N + 1)
finv = [0] * (N + 1)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

for i in range(2, N + 1):
	fac[i] = fac[i - 1] * i % const
	inv[i] = inv[const % i] * (const - (const // i)) % const
	finv[i] = finv[i - 1] * inv[i] % const

ans = 0
i = 0
while H - A - i > 0 and W - B - i > 0:
	ans += fac[H - A + B] * finv[B + i] * finv[H - A - i] * fac[W - B + A] * finv[A + i] * finv[W - B - i]
	ans %= const
	i += 1

if H - A - i == 0:
	ans += fac[W - B + A] * finv[A + i] * finv[W - B - i]
else:
	ans += fac[H - A + B] * finv[B + i] * finv[H - A - i]

ans %= const
print(ans)

Submission status: Accepted

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

class Combination:
    def __init__(self, size, 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, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.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 factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

comb = Combination(H + W + 100)

ans = 0

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

print(ans)

Submission status: Accepted

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

MAXN = H+W+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+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-A+W-2-i, W-1-i) * ncr(A-1+i, i)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
mod = 10**9 + 7
N = 200001
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


def 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

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

    ans += (cmb(B+i-2, B-1, mod)) * cmb((W-B-1) + (H-i), W-B-1, mod)
    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 = 10**9+7
N = max(H,W)*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)

L1 = []
for i in range(W-B):
    L1.append(cmb(H-A-1+B+i, H-A-1, mod))
    


answer = 0
for i in range(len(L1)):
    answer = (answer + L1[i]*cmb(A+W-B-2-i, A-1, mod)) % mod

print(answer)

Submission status: Accepted

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

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

#C(n,r,p) = ( n! * r!^(p-2) * (n-r)!^(p-2) )%p
#pythonだとpow()で二分累乗法が使える
def comb(n, r, p):
  return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p

#紫点ごとに調べる
ans=0
for i in range(b, w):
  ans+= comb(h+i-a-1, i, mod) * comb(w-1-i+a-1, a-1, mod) % mod

print(ans%mod)

Submission status: Accepted

Solution code:
def factorials(n,m):
    # 0~n!のリスト
    f = [1,1]
    for i in range(2,n+1):
        f.append(f[-1]*i%m)

    # 0~n!の逆元のリスト
    g = [1]
    for i in range(n):
        g.append(pow(f[i+1],m-2,m))

    return f,g

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

f,g = factorials(h+w,10**9+7)

ans = 0

for i in range(b,min(w,h-a+b)):
    ans += f[h+b-a-1]*g[h+b-a-1-i]*g[i] * f[w+a-b-1]*g[a-b+i]*g[w-i-1]
    ans %= 10**9+7

print(ans)


"""# nCr mod mを求める
nCr = f[n]*g[n-r]*g[r]
nCr %= m
"""

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)
    ans = 0
    x, y = H - A - 1, W + A - 2
    for i in range(B, W):
        ans += comb(x + i, i) * comb(y - i, A - 1)
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

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)
    ans = 0
    for i in range(B, W):
        ans += comb(i + H - A - 1, i) * comb(W - i - 1 + A - 1, A - 1)
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

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)
    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:
# ARC058D - いろはちゃんとマス目 / Iroha and a Grid (ABC042D)
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
wall = [0 for _ in range(H - A)]
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 combi(self,n,k):
        return self.f[n]*self.i[n-k]%mod*self.i[k]%mod
f = Factorial(H + W, mod)
for i in range(H - A):
  wall[i] = f.combi(B + i - 1, i) * f.combi(W + H - B - i - 2, W - B - 1) % mod
print(sum(wall) % mod)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
MOD=10**9+7
max_n=10**5*2
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%MOD
    inv[n]=MOD-inv[MOD%n]*(MOD//n)%MOD
    ifac[n]=(ifac[n-1]*inv[n])%MOD
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%MOD
a=0
for i in range(min(H-A,W-B)):
    a+=comb(H-A+B-1,B+i)*comb(W-B+A-1,W-B-i-1)
    a%=MOD
print(a)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def init(n):
    # 階乗とその逆元をグローバルに定義
    global factorial, inverse
    # 0-indexedでそれぞれ１で初期化
    factorial = [1]*(n+1)
    inverse = [1]*(n+1)

    fact = 1
    for p in range(1,n+1):
        fact *= p
        fact %= mod
        factorial[p] = fact

    inv = pow(fact, mod-2, mod)
    inverse[n] = inv
    for p in range(2,n+1)[::-1]:
        inv *= p
        inv %= mod
        inverse[p-1] = inv

def comb(n,r):
    if n < r:
        return 0
    return factorial[n] * inverse[n-r] * inverse[r] % mod

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

init(10**6)

def cal(i,j):
    return comb(i+j,i)

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

ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)

H, W, A, B = map(int, input().split())
MOD = 10**9 + 7
com = Combinatorics(H+W, MOD)
ans = com.binom(H-1+W-1, H-1)
for j in range(B):
    ans = (ans - com.binom(H-A-1+j, j) * com.binom(A-1+W-j-1, A-1)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


# 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


def get_gates(h, w, a, b):
    i = 0
    gates = []
    while h-a-1-i >= 0 and b+i < w:
        gates.append((h-a-1-i, b+i))
        i += 1

    return gates


h, w, a, b = li()
MOD = 10**9 + 7

gates = get_gates(h,w,a,b)

inv = inv_mod(h+w, MOD)
fac = fact(h+w, MOD)
facInv = fact_inv(h+w, inv, MOD)

ans = 0
for ri, ci in gates:
    ans += nCr(ri+ci, ci , MOD, fac, facInv) * nCr(h+w-2-(ri+ci), w-1-ci, MOD, fac, facInv)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
mod=10**9+7
kaijo=[0]*(H+W+1)
kaijo[0]=1
for i in range(1,H+W+1):
    kaijo[i]=(kaijo[i-1]*i)%mod
gyaku=[0]*(H+W+1)
gyaku[H+W]=pow(kaijo[H+W],mod-2,mod)
for i in range(H+W,0,-1):
    gyaku[i-1]=(gyaku[i]*i)%mod
def conb(x,k):
    return (kaijo[x]*gyaku[k]*gyaku[x-k])%mod
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))%mod
print(ans)

Submission status: Accepted

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

# See:
# http://drken1215.hatenablog.com/entry/2018/06/08/210000
max_value = 500050
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]


def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

    for i in range(2, max_value):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


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


def main():
    h, w, a, b = map(int, input().split())
    x = h - (a + 1)
    com_init()
    prev = 0
    ans = 0
    com_xy = [0 for _ in range(w - b)]
    com_za = [0 for _ in range(w - b)]
    i = 0
    j = 0

    for y in range(b, w):
        com_xy[i] = com(x + y, y)
        i += 1

    for z in range((w - (b + 1) + a), a - 1, -1):
        com_za[j] = com(z, z - a)
        j += 1

    for xy, za in zip(com_xy, com_za):
        ans += (xy - prev) * za
        ans %= mod
        prev = xy

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

H,W,A,B = map(int,input().split())
fac = [0]*(H+W)
finv = [0]*(H+W)
inv = [0]*(H+W)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,H+W):
        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
ans = 0
for x in range(W-B):
    if x == 0:
        ans += ((comb(H-A-1+B+x,B+x))*comb(A+W-1-B-x,A))
    else:
        ans += ((comb(H-A-1+B+x,B+x)-comb(H-A-1+B+x-1,B+x-1))*comb(A+W-1-B-x,A))
    ans %= mod
print(ans)

Submission status: Accepted

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


MOD = 10 ** 9 + 7
M = 200005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
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)
    rfact[i] %= MOD


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


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

print(ans)

Submission status: Accepted

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

MOD = 1000000007  # type: int

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

    F = [0] * (H + W + 1)
    F[0] = 1
    for i in range(1, H + W + 1):
        F[i] = (F[i-1] * i) % MOD
    F2 = [0] * (H + W + 1)
    F2[0] = 1
    for i in range(1, H+W+1):
        F2[i] = (F2[i-1] * pow(i, MOD-2, MOD)) % MOD
    def nck(a, b):
        if a == 0 and b == 0:
            return 1
        return (F2[a-b] * F2[b] % MOD) * F[a] % MOD
    total = nck(H+W-2, H-1)
    removed = 0
    for k in range(A):
        removed += nck(H-k-1+B-1, H-k-1) * nck(k+W-B-1, k)
        removed %= MOD
    res = (total - removed) % MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 1000000007
H, W, A, B = map(int, input().split())
if H - A > W - B:
    H, W = W, H
    A, B = B, A
#print(H, W, A, B)
ans1 = [1]
for i in range(H - A - 1):
    #print(ans1)
    ans1.append((ans1[-1] * (H - A - 1 + B - i) * pow(i + 1, MOD - 2, MOD)) % MOD)
#print(ans1)
c = 1
for i in range(W - H + A - B):
    c = (c * (W - B - 1 + A - i) * pow(i + 1, MOD - 2, MOD)) % MOD
ans = c
for i in range(H - A - 1):
    #print(ans)
    c = (c * (H - 1 - i) * pow(W - H + A - B + 1 + i, MOD - 2, MOD)) % MOD
    ans = (ans + c * ans1[i + 1]) % MOD
print(ans)

Submission status: Accepted

Solution code:
class BigCombination(object):
    __slots__ = ["mod", "factorial", "inverse"]
 
    def __init__(self, mod  = 10**9+7, max_n = 10**6):
        fac, inv = [1], []
        fac_append, inv_append = fac.append, inv.append
 
        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)
 
        inv_append(pow(fac[-1], mod-2, mod))
 
        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)
 
        self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]
 
    def get_combination(self, n, r):
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod
 
    def get_permutation(self, n, r):
        return self.factorial[n] * self.inverse[n-r] % self.mod
 
 
import math
Big = BigCombination()
mod=10**9+7
h,w,a,b=map(int,input().split())
ans=0
for i in range(b,w):
    ans=(ans+ Big.get_combination(h-a-1+i,i)* Big.get_combination(a-1+w-i-1,w-i-1))%mod
print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
MAX = H + W
MOD = 10 ** 9 + 7
fac = [0 for _ in range(MAX)]
finv = [0 for _ in range(MAX)]
inv = [0 for _ in range(MAX)]
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 COM(n, k):
    global fac
    global finv
    global MOD
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def route(h, w):
    return COM(h + w - 2, h - 1)


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

Submission status: Accepted

Solution code:
class COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

    def comb(self, n, k):
        if n < k : return 0
        if n < 0 or k < 0:return 0
        return self.fac[n] * (self.finv[k] * self.finv[n-k] % self.mod) % self.mod
mod = 10**9 + 7
h,w,a,b = map(int,input().split())
C = COMB_MOD(max_n=2*10**5)
ans = 0
for i in range(h-a):
    ans = (ans + C.comb(b-1+i,i)*C.comb(h-1-i+w-1-b,h-1-i))%mod
print(ans)