Problem:


Score : 400 points

Problem Statement

We have a large square grid with H rows and W columns.
Iroha is now standing in the top-left cell.
She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.

However, she cannot enter the cells in the intersection of the bottom A rows and the leftmost B columns. (That is, there are A×B forbidden cells.) There is no restriction on entering the other cells.

Find the number of ways she can travel to the bottom-right cell.

Since this number can be extremely large, print the number modulo 10^9+7.

Constraints

 1 ≦ H, W ≦ 100,000

 1 ≦ A < H

 1 ≦ B < W

Input

The input is given from Standard Input in the following format:

H W A B

Output

Print the number of ways she can travel to the bottom-right cell, modulo 10^9+7.

Sample Input 1

2 3 1 1

Sample Output 1

2

We have a 2×3 grid, but entering the bottom-left cell is forbidden. The number of ways to travel is two: "Right, Right, Down" and "Right, Down, Right".

Sample Input 2

10 7 3 4

Sample Output 2

3570

There are 12 forbidden cells.

Sample Input 3

100000 100000 99999 99999

Sample Output 3

1

Sample Input 4

100000 100000 44444 55555

Sample Output 4

738162020



Sample input:
2 3 1 1


Sample output:
2

Submission status: Accepted

Solution code:
import sys

def comb(n, r, mod=None):
    if r == 0 or r == n:
        return 1
    r = min([r, n-r])
    x, y = 1, 1
    ans = 1
    for i in range(1, r+1):
        if mod:
            x *= n+1-i
            y *= i
            x %= mod
            y %= mod
        else:
            ans *= n+1-i
            ans //= i
    ans = x*pow(y, mod-2, mod)%mod if mod else ans
    return ans

def main():
    input = sys.stdin.readline
    h, w, a, b = map(int, input().split())
    mod = pow(10, 9)+7
    
    bef, aft = 1, comb(h+w-b-2, h-1, mod)
    ans = 0
    for i in range(h-a):
        ans += bef*aft
        ans %= mod
        
        bef = bef*(i+b)*pow(i+1, mod-2, mod)%mod
        aft = aft*(h-i-1)*pow(h-i+w-b-2, mod-2, mod)%mod
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7
UPPERLIMIT=2*(10**5)+1
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD

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

ans=(((MODMUL[H+W-2]*MODDIV[H-1])%MOD)*MODDIV[W-1])%MOD

x=[MODMUL[H-A+B+i-1]*MODDIV[B-1]*MODDIV[H-A+i]%MOD for i in range(A)]
y=[MODMUL[W+A-B-i-1]*MODDIV[W-B]*MODDIV[A-i-1]%MOD for i in range(A)]
for i in range(A-1, 0, -1):
  x[i]-=x[i-1]

for i in range(A):
  ans-=(x[i]*y[i]%MOD)
  ans%=MOD
  
print(ans)

Submission status: Accepted

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

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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1
for i in range(2, MAX + 1):
    fac[i] = fac[i - 1] * i % MOD
    
# Inverse factorial
finv = [0] * (MAX + 1)
finv[MAX] = pow(fac[MAX], MOD - 2, MOD)
for i in reversed(range(1, MAX + 1)):
    finv[i - 1] = finv[i] * i % MOD


def comb(a, b):
    return fac[a + b] * finv[a] * finv[b]


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

print(ans)

Submission status: Accepted

Solution code:

a,b,c,d = list(map(int, input().split()))

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9+7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def wh(w,h):
    return cmb(w+h,w,10**9+7)

ans = wh(b-1,a-1)
#print(ans)

for i in range(d):
    tmp = wh(i,a-c-1) * wh(c-1,b-i-1) % p
    ans += p
    ans -= tmp
    ans %= p
    #print(ans)
    
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def pathVar(sx, sy, gx, gy):
    x = gx - sx
    y = gy - sy
    rst = modFacts[x + y]
    rst *= invs[x] * invs[y]
    rst %= MOD
    return rst


H, W, A, B = map(int, input().split())
# H -= 1; W -= 1
modFacts, invs = prepare(H + W)

cnt = 0
while A > 0 and B > 0:
    x = H - A
    y = B - 1
    path1 = pathVar(0, 0, x, y)
    path2 = pathVar(x, y, H - 1, W - 1)
    cnt += path1 * path2
    cnt %= MOD
    A -= 1; B -= 1

ans = pathVar(0, 0, H - 1, W - 1)
print((ans - cnt) % MOD)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque
import itertools
#from scipy.misc import comb

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

def comb(a,b):
	p = fac[a-b]*fac[b]%MOD
	return fac[a]*pow(p,MOD-2,MOD)%MOD

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

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

print(ans)

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
inv=[0]*(2*max(h,w)+1)
fact=[0]*(2*max(h,w)+1)
inv[0]=1;fact[0]=1
mod=10**9+7
for i in range(1,2*max(h,w)+1):
    fact[i]=fact[i-1]*i%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(2*max(h,w),0,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
for yoko in range(b+1,w+1):
    re=fact[yoko-1+h-1-a]*inv[h-1-a]*inv[yoko-1]%mod
    rr=fact[w-yoko+a-1]*inv[w-yoko]*inv[a-1]%mod
    ans=(ans+re*rr%mod)%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)

Submission status: Accepted

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

H, W, A, B = [int(i) for i in input().split(" ")]

ans = 0
# 経路の足し上げ C(縦+横, 縦(or横)) (重複のある組み合わせ)
for i in range(B, W):
    ans += comb((H-A-1) + i, i) * comb((A - 1) + (W-1-i), W-1- i) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


h, w, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
facts, invs = prepare(h + w, MOD)
ans = 0
ib = invs[b - 1]
iwb = invs[w - b - 1]
for down in range(h - a):
    left_pattern = facts[b - 1 + down] * ib * invs[down] % MOD
    right_pattern = facts[h - 1 - down + w - b - 1] * invs[h - 1 - down] * iwb % MOD
    ans = (ans + left_pattern * right_pattern) % MOD
print(ans)

Submission status: Accepted

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

fact = [1] * (H+W+1)
fact_inv = [1] * (H+W+1)
for i in range(1, H+W+1):
    fact[i] = i * fact[i-1] % mod
fact_inv[H+W] = pow(fact[H+W], mod-2, mod)
for i in range(1, H+W+1)[::-1]:
    fact_inv[i-1] = i * fact_inv[i] % mod
comb = lambda n, k: fact[n] * fact_inv[k] * fact_inv[n-k] % mod

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

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
fac_table = [1 for i in range(200001)]
inv_table = [1 for i in range(200001)]


def make_table(h, w):

    for i in range(1, h + w - 1):
        fac_table[i] = fac_table[i - 1] * i % mod
        inv_table[i] = pow(fac_table[i], mod - 2, mod)


def comb(n, r):
    return fac_table[n] * inv_table[n - r] % mod * inv_table[r] % mod


def resolve():
    H, W, A, B = map(int, input().split())
    make_table(H, W)
    print(
        sum(
            [
                comb(H - A - 1 + i, i) * comb(A - 1 + W - i - 1, A - 1) % mod
                for i in range(B, W)
            ]
        )
        % mod
    )

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

factorial = [1 for _ in range(U + 1)]
for i in range(1, U + 1):
    factorial[i] = (factorial[i - 1] * i) % mod

inverse = [1 for _ in range(U + 1)]
inverse[U] = pow(factorial[U], mod - 2, mod)
for i in range(U, 0, -1):
    inverse[i - 1] = (inverse[i] * i) % mod


def comb(n, k):
    if k < 0 or k > n:
        return 0
    x = factorial[n]
    x *= inverse[k]
    x %= mod
    x *= inverse[n - k]
    x %= mod
    return x
  
  
ans = 0
for i in range(H - A):
    x = comb(B - 1 + i, i)
    a = H - 1 - i
    b = W - 1 - B
    x *= comb(a + b, a)
    x %= mod
    ans += x
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
import time

DIV_VALUE = 10**9 + 7

def calcModOfPow(a, n, p):
    btm = a
    ans = 1
    while n != 0:
        # print('btm: {}'.format(btm))
        if n & 1:
            ans = (ans * btm) % p
            # print('ans: {}'.format(ans))
        n = n>>1
        btm = (btm**2) % p
        # print(n)

    return ans

def calcModOfInv(a, p):
    b = p
    x = 1
    y = 0
    while b:
        div = a // b
        a -= div * b
        [a, b] = [b, a]
        x -= div * y
        [x, y] = [y, x]
    
    x %= p
    if x < 0:
        x += p

    return x

class FirstHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.sup = 0
        self.numOfCases = 1

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                (self.B + self.k - 1)
            ) * (
                calcModOfInv(self.k, DIV_VALUE)
            ) % DIV_VALUE
        self.k += 1
        # print('----- k == {} -----'.format(self.k))
        # print(self.numOfCases)
        # self.numOfCases %= DIV_VALUE
        return self.numOfCases
        # return self.numOfCases % DIV_VALUE

class SecondHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.numOfCases = 1
        totalval = self.H + self.W - self.B - 2
        loopval = self.H - 1 if self.H < self.W - self.B else self.W - self.B - 1
        for top in range(totalval, totalval - loopval, -1):
            self.numOfCases *= top
            self.numOfCases %= DIV_VALUE
        for bottom in range(loopval, 0, -1):
            self.numOfCases *= calcModOfInv(bottom, DIV_VALUE)
            self.numOfCases %= DIV_VALUE

        # self.numOfCases = (
        #     math.factorial(self.H + self.W - self.B - 2)
        # ) // (
        #     math.factorial(self.W - self.B - 1)
        # ) // (
        #     math.factorial(self.H - 1)
        # )

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                self.H - self.k
            ) * (
                calcModOfInv(
                    self.H + self.W - self.B - self.k - 1,
                    DIV_VALUE
                )
            ) % DIV_VALUE
        self.k += 1
        # print(self.numOfCases)
        # self.numOfCases %= DIV_VALUE
        return self.numOfCases
        # return self.numOfCases % DIV_VALUE

if __name__ == '__main__':
    [H, W, A, B] = [int(ipt) for ipt in input().split()]
    
    start = time.time()
    fstHlf = FirstHalf(H, W, A, B)
    sndHlf = SecondHalf(H, W, A, B)
    totalCases = 0

    mid = time.time()
    # print('mid: {}'.format(mid - start))
    for _ in range(H - A):
        totalCases += (
            fstHlf.getNumOfCases() * sndHlf.getNumOfCases()
        )
        totalCases %= DIV_VALUE

    end = time.time()
    # print('end: {}'.format(end - mid))
    print(totalCases)

    #print('{} {} {} {}'.format(H, W, A, B))
    #print(DIV_VALUE)

    # for i in range(12):
    #     print('inv: {}'.format(calcModOfInv(i+1, 13)))

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    H, W, A, B = map(int, input().split())
    mod = 10**9 + 7
    c = cmbs(mod)
    r = c.cmb(H+W-2, H-1)
    for i in range(1, B+1):
        r -= c.cmb(H-A+i-2, i-1) * c.cmb(A-1+W-i, A-1)
    return r % mod
print(main())

Submission status: Accepted

Solution code:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    H, W, A, B = map(int, input().split())
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    r = 0
    a = H - A - 1
    for i in range(B, W):
        r = (r + nCr(a + i, i) * nCr(A - 1 + W - i - 1, W - i - 1)) % mod
    return r


print(main())

Submission status: Accepted

Solution code:
class CombinationFermat:

    def __init__(self):
        """O(MAX)で前計算しておく→以降comb(a,b)はO(1)で取得可能
        """
        MOD = 10**9 + 7
        MAX = 2*10**5

        self.fac = [0]*MAX   # self.fac[n]:  (n!) mod p
        self.finv = [0]*MAX  # self.finv[n]: (n!)^-1 mod p
        self.inv = [0]*MAX   # inv[n]:  (n)^-1 mod -p
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        for i in range(2, MAX):
            self.fac[i] = self.fac[i-1] * i % MOD
            self.inv[i] = MOD - self.inv[MOD % i] * (MOD//i) % MOD
            self.finv[i] = self.finv[i-1] * self.inv[i] % MOD

    def comb(self, n: int, r: int) -> int:
        MOD = 10**9 + 7
        if n < r:
            return 0
        if n < 0 or r < 0:
            return 0
        return self.fac[n] * (self.finv[r] * self.finv[n-r] % MOD) % MOD


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

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX = 2*10**5
fac = [0]*MAX  # fac[n]:  (n!) mod p
finv = [0]*MAX  # finv[n]: (n!)^-1 mod p
inv = [0]*MAX  # inv[n]:  (n)^-1 mod -p


def comb_init():
    global fac, finv, inv
    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: int, r: int) -> int:
    global fac, finv
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD


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

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

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

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

        self.fact = fact
        self.invs = invs
        self.mod = mod

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


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

    calc = Calc(max_value=H + W, mod=MOD)

    ans = 0
    for x in range(B, W):
        v = calc.combination(n=(H - A - 1) + x, r=x)
        u = calc.combination(n=(A - 1) + (W - 1 - x), r=A - 1)
        # (H-1)-(H-A)+(W-1)-x
        ans = (ans + v * u) % MOD
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 2 * 10 ** 5 + 1000  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

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

Submission status: Accepted

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

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

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

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

    ans = cmb((H+W-2), min(H, W)-1, mod)

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


main()

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# grobalにmdを設定すること
class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    h,w,a,b=MI()
    cc=[]
    for i in range(h-a):
        cc.append(nCr(b+i,i))
    #print(*cc)
    ans=mint(0)
    pc=0
    for i,c in enumerate(cc):
        ans+=(c-pc)*nCr(h-1-i+w-1-b,w-1-b)
        pc=c
    print(ans)

main()

Submission status: Accepted

Solution code:
def cmb1(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())
 
# 前処理
mod=10**9+7 #出力の制限
n=10**6
g1=[1,1] # 元テーブル
g2=[1,1] # 逆元テーブル
inverse=[0,1] #逆元テーブル計算用テーブル
 
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

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

Submission status: Accepted

Solution code:
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 nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

H, W, A, B = map(int, input().split())
comb = Combination(H + W + 100)
MOD = 10**9 + 7

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 2 * 10 ** 5 + 100  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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


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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    f = [1]
    N = 1000000
    for i in range(1,N+1):
        f.append(f[-1]*i%mod)
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(N)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    def comb(a,b):
        return f[a]*inv[b]*inv[a-b]%mod
    h,w,a,b = LI()
    ans = 0
    y = h-a
    x = b+1
    while x <= w and y:
        ans += comb(x+y-2,x-1)*comb(h-y+w-x,w-x)%mod
        y -= 1
        x += 1
    print(ans%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
memo=[0]*(10**6+1)
memo[0]=memo[1]=1
mod=10**9+7
for i in range(2,10**6+1):
  memo[i]=(memo[i-1]*i)%mod
def comb(n,k,p):
  return (memo[n]*pow(memo[k],p-2,p)*pow(memo[n-k],p-2,p))%mod
h,w,a,b=map(int,input().split())
ans=0
for i in range(h-a):
  ans+=(comb(b+i-1,i,mod)*comb(h-i-1+w-b-1,w-b-1,mod))%mod
  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)

Submission status: Accepted

Solution code:

# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def gcd(b, m):
  if b == 0:
    return m
  return gcd(m%b, b)

def modInverse(b,m): 
    g = gcd(b, m) 
    if (g != 1): 
        # print("Inverse doesn't exist")  
        return -1
    else:  
        # If b and m are relatively prime,  
        # then modulo inverse is b^(m-2) mode m  
        return pow(b, m - 2, m) 
  
  
# Function to compute a/b under modulo m  
def modDivide(a,b,m): 
    a = a % m 
    inv = modInverse(b,m) 
    if(inv == -1): 
        print("Division not defined") 
    else: 
        return (inv*a) % m

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

DP = []
j = 1
for i in range(1,200002):
    j *= i
    j %= MOD
    DP.append(j)

# print(DP)
def factorial(i):
    if (i == 0):
        return 1
    global DP
    # print(i)
    # print(i, DP[i-1])
    # print(DP[i-1])
    return DP[i-1]

def move2(H, W, A, B):
    numPaths = 0
    h = H-A
    w = W-(W-B)+1
    a = A+1
    pttp = 0
    for b in range(w, W+1):
        # print(h, b, a, W-b+1)
        ttp = (factorial(h+b-2)*modInverse((factorial(h-1)*factorial(b-1))% MOD, MOD)) % MOD
        tpttp = ttp
        ttp -= pttp
        pttp = tpttp
        btp = (factorial(a+(W-b+1)-2)*modInverse((factorial(a-1)*factorial(W-b))% MOD, MOD)) % MOD
        # btp = factorial(a+(W-b+1)-2)//(factorial(a-1)*factorial(W-b))
        numPaths += ttp*btp
    return numPaths

ways = move2(H, W, A, B)
print(ways % (10**9 + 7))

Submission status: Accepted

Solution code:
MOD = 10**9+7

def modpow(base, pow, mod):
  res = 1
  while pow > 0:
    if pow & 1:
      res = res * base % mod
    base = base**2 % mod
    pow >>= 1
  return res

def modmul(a, b, mod):
  return a*b % mod

def solve(h,w,a,b):
  fact = [0]*(h+w+1)
  fact[0] = 1
  fact_inv = [0]*(h+w+1)
  fact_inv[0] = 1
  for i in range(1, h+w):
    fact[i] = fact[i-1]*i % MOD
    fact_inv[i] = modpow(fact[i], MOD-2, MOD)

  ans = 0
  for col_idx in range(b, w):
    before_checkpoint = modmul(modmul(fact[h-a-1+col_idx], fact_inv[h-a-1], MOD), fact_inv[col_idx], MOD)
    from_checkpoint = modmul(modmul(fact[(a-1) + (w-col_idx-1)], fact_inv[w-col_idx-1], MOD), fact_inv[a-1], MOD)
    ans = (ans + modmul(before_checkpoint, from_checkpoint, MOD)) % MOD

  return ans

if __name__ == "__main__":
  h,w,a,b = map(int, input().split())
  print(solve(h,w,a,b))

Submission status: Accepted

Solution code:
h, w, a, b = [int(i) for i in input().split()]

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


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


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