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
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1)
        invfact=[1]*(n+1)
        for i in range(1,n+1):
            fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1):
            invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact
        self.__invfact=invfact

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n-k<0): return 0
        return (self.fact(n)*self.invfact(k)*self.invfact(n-k))%MOD

def resolve():
    h,w,a,b=map(lambda x:int(x)-1,input().split())
    mf=modfact(h+w)
    ans=mf.comb(h+w,h)
    for j in range(b+1):
        i=(h-a)+b-j
        ans-=mf.comb(i+j,i)*mf.comb(h-i+w-j,h-i)%MOD
    print(ans%MOD)
resolve()

Submission status: Accepted

Solution code:
U = 2*10**6
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
  z = fact[n]
  z *= fact_inv[k]
  z %= MOD
  z *= fact_inv[n-k]
  z %= MOD
  return z

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

Submission status: Accepted

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

t_mod = [1] * (h+w-1) 
for i in range(1, h+w-1):
    t_mod[i] = i * t_mod[i-1] % mod 

t_modinv = list(map(lambda v: pow(v, mod-2, mod), t_mod))

def comb(n, r):
    return t_mod[n] * t_modinv[r] * t_modinv[n-r] % mod

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

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#str 注意

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv


def main():
    h,w,a,b = map(int,input().split())
    cmb = Combination(10**6)
    roop = min(h-a,w-b)
    ans = 0
    for i in range(roop):
        before = cmb(h-a+b-1,b+i) % (10**9+7)
        after  = cmb(w+a-b-1,a+i) % (10**9+7)
        ans  = (ans+(before*after)%(10**9+7)) % (10**9+7)
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#cmb
mod=10**9+7
MAX=2*10**5+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

h,w,a,b=map(int,input().split())
ans=0
for i in range(1,h-a+1):
    ans=(ans+cmb(i+b-2,i-1,mod)*cmb(h-i+w-b-1,h-i,mod))%mod

print(ans)

Submission status: Accepted

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

    # 予め階乗を計算しておく
    f = [1]
    for i in range(H+W):
        f.append(f[i]*(i+1)%mod)

    # 組み合わせ関数
    def comb_mod(n, r, p):
        return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

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

    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * 200005
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD
h, w, a, b = map(int, input().split())
ans = 0
x, y = b, h - a - 1
while x < w and y >= 0:
    p = w - x - 1
    q = h - y - 1
    ans += (fac[x + y] * pow(fac[x] * fac[y], MOD - 2, MOD) *
            fac[p + q] * pow(fac[p] * fac[q], MOD - 2, MOD)) % MOD
    x += 1
    y -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
n=200000
mod=10**9+7
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
h,w,a,b=map(int,input().split())
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)

Submission status: Accepted

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

N = H+W+1

def power(base, num):
    if num == 0:
        return 1
    elif num % 2==0:
        return power(base, num//2) **2 % MOD
    elif num==1:
        return base % MOD
    else:
        return power(base, num//2) **2 * base % MOD

fact = [0 for i in range(N)]
inv_fact = [0 for i in range(N)]

fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i-1] * i % MOD
    
inv_fact[H+W] = power(fact[H+W], MOD-2)
for i in range(1, N):
    inv_fact[N-1-i] = inv_fact[N-i] * (N-i) % MOD

    
def comb(x,y):
    return (fact[x] * inv_fact[y])%MOD * inv_fact[x-y] % MOD

ans = 0

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

Submission status: Accepted

Solution code:
def examD(mod):
    class combination():
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

    H, W, A, B =LI()
    N = H + W
    C = combination(N,mod)
    ans = C.comb(W+H-B-2, H-1,mod)
    pre = 1
    for i in range(1, H-A):
        ans += (C.comb(B+i,i,mod)-pre)*C.comb(W+H-B-2-i, H-1-i,mod)%mod
        ans %= mod
        pre = C.comb(B+i, i,mod)
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD(mod)

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = h+w
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 j in range(b,w):
  ans += cmb(h-a-1+j, j, mod) * cmb(a-1+w-j-1, a-1, mod)
print(ans%mod)

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def extgcd(a, b):
    x, y = 0, 0

    def f(a, b):
        nonlocal x, y
        if b == 0:
            x = 1
            y = 0

            return a

        g = f(b, a % b)
        q = a // b
        next_x = y
        y = x - q * y
        x = next_x
        return g

    g = f(a, b)
    return x, y, g


fact = [0] * 200010
invfact = [0] * 200010
mod = 10 ** 9 + 7


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


fact[0] = 1
for i in range(1, 200000 + 1):
    fact[i] = (fact[i - 1] * i) % mod
for i in range(200000 + 1):
    x, y, g = extgcd(fact[i], mod)
    while x < 0:
        x += mod
    invfact[i] = x % mod

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

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

Submission status: Accepted

Solution code:
import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N= [0]*(H+W)
N[H+W-1] = power(M[H+W-1], e-2)
for i in range(H+W-2, -1, -1):
    N[i] = N[i+1] * (i+1) % e

def c(a,b):
    return M[a]*N[b]*N[a-b]%e

T = 0
for i in range(W-B):
    P = c(H+W-A-i-2,H-A-1)
    Q = c(A+i-1,i)
    T = (T + P*Q)
print(T%e)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, a, b = LI()
n = h + w

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


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


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


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


print(ans)

Submission status: Accepted

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

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

stairs = [1]
for i in range(1, h+w+1):
    stairs.append(stairs[i-1]*i%mod)

inverse_stairs = [0]*(h+w)
inverse_stairs[h+w-1] = modpow(stairs[h+w-1], mod-2)
for i in range(h+w-2, -1, -1):
    inverse_stairs[i] = inverse_stairs[i+1] * (i+1) % mod
    
ret = 0
for i in range(w-b):
    com = stairs[w-i+h-a-2]%mod
    com = com*inverse_stairs[w-i-1]%mod
    com = com*inverse_stairs[h-a-1]%mod
    com = com*stairs[i+a-1]%mod
    com = com*inverse_stairs[i]%mod
    com = com*inverse_stairs[a-1]%mod
    ret += com

print(ret%mod)

Submission status: Accepted

Solution code:
# D　イロハちゃんと升目
cnt=0
h,w,a,b=map(int,input().split())
def find_power(n):
    # 0!からn!までのびっくりを出してくれる関数
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

powlist=find_power(h+w+1)
invlist=find_inv_power(h+w+1)
def combi(n,r):
    a=powlist
    b=invlist
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(10**9+7)

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

Submission status: Accepted

Solution code:
MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            # self.inverses.append(mod_inverse(i, self.mod))
            self.inverses.append(self.mod - self.inverses[self.mod % i] * (
                        self.mod // i) % self.mod)
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


def check(h, w, a, b):
    combination = ModCombination(mod=MOD, n_max=h + w)
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(combination, *d1)
        r2 = calc_routes(combination, *d2)
        routes = r1 * r2 % MOD
        all_routes += routes
        all_routes %= MOD
        p = (p[0] + 1, p[1] - 1)
    return all_routes


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    x = fact[n] * fact_inverse[r] % mod
    x = x * fact_inverse[n - r] % mod
    return x


def d_cmb(n, r, mod):
    return mod_cmb(n + r - 1, r, mod)


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


fact = [1] * (limit + 1)
fact_inverse = [1] * (limit + 1)

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

fact_inverse[limit] = mod_pow(fact[limit], MOD - 2, MOD)
for i in reversed(range(1, limit + 1)):
    fact_inverse[i - 1] = fact_inverse[i] * i % MOD

n1 = W
r1 = H - A - 1
n2 = 1
r2 = A - 1
ans = 0
for i in range(W - B):
    ans += d_cmb(n1 - i, r1, MOD) * d_cmb(n2 + i, r2, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def modpow(a, n, mod):
  res = 1
  while n > 0:
    if (n & 1):
      res = res * a % mod
    a = a * a % mod
    n >>= 1
  return res

DIV = 10**9 + 7
h, w, a, b = map(int, input().split())
ans = 0
#最大h+w!までの元と逆元の階乗テーブルを求めておく
#逆元をFermatの小定理により計算
#p-2乗は二分累乗法にて高速に計算可能
table = [1 for i in range(h + w + 1)]
inv_table = [1 for i in range(h + w + 1)]
temp = 1
for i in range(1, h + w + 1):
  temp = temp * i % DIV
  table[i] = temp
  inv_table[i] = modpow(temp, DIV - 2, DIV)

for i in range(w - b):
  n1 = table[h + i + b - a - 1] * inv_table[b + i] * inv_table[h - a - 1] % DIV
  n2 = table[w + a - b - 2 - i] * inv_table[a - 1] * inv_table[w - b - 1 - i] % DIV
  ans += n1 * n2 % DIV
ans = int(ans)
print(ans%DIV)

Submission status: Accepted

Solution code:
import operator as op
from functools import reduce

MOD = (10 ** 9) + 7

factors = [1, 1]
finv = [1, 1]
inv = [0, 1]

for i in range(2, 200010):
    factors.append(factors[i - 1] * i % MOD)
    inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)
    finv.append(finv[i - 1] * inv[i] % MOD)

def nck(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    return factors[n] * (finv[k]  * finv[n - k] % MOD) % MOD

def ncr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

assert ncr(3, 4) == 0

def g(h, w, a, b):
    prev = [1] * w
    cur = [0] * w

    for i in range(h - 1):
        cur[0] = 1
        start = 0
        if i >= h - 1 - a:
            cur[b] = prev[b]
            start = b
        for j in range(start + 1, w):
            cur[j] = cur[j - 1] + prev[j]
            cur[j] = cur[j] % (1e9 + 7)
        prev, cur = cur, prev
    return prev[-1]

def f(H, W, A, B):
    count = 0
    x, y, a = H - A - 1, W + A - 2, A - 1
    for i in range(B, W): # bottom-left to top-right
        c1 = nck(x + i, i)
        c2 = nck(y - i, a)
        c = c1 * c2
        count += c
        count = count % MOD
    return int(count)

## assert f(4, 4, 0, 0) == 20
# assert f(4, 4, 2, 2) == 10
#assert f(2, 3, 1, 1) == 2
#assert f(10, 7, 3, 4) == 3570
#assert f(100000, 100000, 99999, 99999) == 1
#assert f(100000, 100000, 44444, 55555) == 738162020

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

Submission status: Accepted

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod
 
 
mod = 10**9+7 #出力の制限
N = 200000
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 = 0
#print(x)

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
factorials = [1]
for i in range(1, 200000):
    factorials.append((factorials[-1] * i) % MOD)
invs = [pow(x, MOD - 2, MOD) for x in factorials]


def combinations(n, k):
    return (factorials[n] * invs[k] * invs[n - k]) % MOD


def f(x, y):
    return combinations(x + y - 2, x - 1)


h, w, a, b = map(int, input().split())
res = 0
for y in range(1, h - a + 1):
    res += (f(b, y) * f(w - b, h - y + 1)) % MOD
print(res % MOD)

Submission status: Accepted

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

mod = 10**9+7 #出力の制限
N = 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 )

#a = cmb(n,r,mod)

H,W,A,B = map(int,input().split())
ret = 0
for i in range(H-A):
    ret += cmb(B-1+i, i, mod)*cmb(W-B-1+H-i-1, W-B-1,mod)
    
print(ret%(10**9+7))

Submission status: Accepted

Solution code:
def main():
    h,w,a,b=map(int,input().split(' '))
    mod = 10**9+7
    mx=max(h,w)
    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__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(1, h-a+1):
    if i == 1:
        t1 = 1
        t2 = 1
        for j in range(1, ((h-a-i)+(b-1)+1)):
            t1 *= j
            t1 %= mod
        for j in range(1, ((b-1)+1)):
            t2 *= j
            t2 %= mod
        for j in range(1, ((h-a-i)+1)):
            t2 *= j
            t2 %= mod
        a1 = t1 * pow(t2, mod-2, mod) % mod

        t1 = 1
        t2 = 1
        for j in range(1, ((w-b-1)+(a+i-1)+1)):
            t1 *= j
            t1 %= mod
        for j in range(1, ((w-b-1)+1)):
            t2 *= j
            t2 %= mod
        for j in range(1, ((a+i-1)+1)):
            t2 *= j
            t2 %= mod
        a2 = t1 * pow(t2, mod-2, mod) % mod
    else:
        a1 *= pow((h-a-i)+(b-1)+1, mod-2, mod) 
        a1 *= h-a-i+1
        a1 %= mod 
        a2 *=  (w-b-1)+(a+i-1) 
        a2 %= mod
        a2 *= pow(a+i-1, mod-2, mod) 
        a2 %= mod
 
    #print(a1, a2)
    ans += a1 * a2 
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
H,W,A,B = map(int,input().split())
MOD = 10**9 + 7
FAC = [1]
INV = [1]
for i in range(1,H+W+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))
#print(FAC)
#print(INV)

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Submission status: Accepted

Solution code:
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I*(W+H-B-1-I))%M;Z+=C
print(Z%M)

Submission status: Accepted

Solution code:
h, w, a, b = map(int, input().split())
res = 0
kai = min(w - b, h - a)
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


conb1 = conb(h - a - 1 + b, b)
conb2 = conb(a + w - b - 1, a)
combi = conb1 * conb2
res = combi

for i in range(1, kai):
    res += conb(h - a - 1 + b, b + i) * conb(a + w - b - 1, a + i)

res %= mod
print(int(res))

Submission status: Accepted

Solution code:
class ModComb:
    def __init__(self, MAX, mod=10 ** 9 + 7):
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, MAX):
            fac.append(fac[i - 1] * i % mod)
            inv.append(mod - inv[mod % i] * (mod // i) % mod)
            finv.append(finv[i - 1] * inv[i] % mod)
        self.fac, self.finv, self.mod = fac, finv, mod

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

mod = 10 ** 9 + 7
mc = ModComb(200010, mod=mod)

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

x, y, a = H - A - 1, W + A - 2, A - 1
print(sum(mc.nCk(x + i, i) * mc.nCk(y - i, a) for i in range(B, W)) % mod)

Submission status: Accepted

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    H,W,A,B = LI()

    ans = [0]*(W-B)

    ans[0] = 1

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

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

    return(sum(ans)%mod)


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

Submission status: Accepted

Solution code:
def d_iroha_and_a_grid(MOD=10**9 + 7):
    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            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 comb(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    H, W, A, B = [int(i) for i in input().split()]
    c = Combination(max_n=H + W)
    # 左上のマスの座標を(0,0)としたとき、B<=i<=W-1を満たすiについて、
    # (0,0)→(H-A-1,i)への行き方 * (H-A-1,i)→(H-A,i)への行き方(1通り) *
    # (H-A,i)→(H-1,W-1)への行き方 の値の総和を取る(10**9+7で剰余を取る)
    ans = sum([c.comb(H - A - 1 + i, H - A - 1)
               * c.comb(A - 1 + W - 1 - i, A - 1) for i in range(B, W)])
    return ans % MOD

print(d_iroha_and_a_grid())

Submission status: Accepted

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

fac = [1 for k in range(200010)]
inv = [1 for k in range(200010)]
finv = [1 for k in range(200010)]

for k in range(2,200010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;

def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD

k = 1
ans = 0
while B+k <= W and H-A-k+1 > 0:
    ans += nCr(B+k-1+(H-A-k),B+k-1) * nCr(W-(B+k) + H-(H-A-k+1),H-(H-A-k+1))
    ans %= MOD
    k += 1
print(ans)

Submission status: Accepted

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

#階乗を求める
fact_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    fact_l[i] *= (fact_l[i-1]*i)%mod

#逆元
factinv_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    factinv_l[i] = pow(fact_l[i],mod-2,mod)
    
#必ず通るポイントまでの組み合わせ
point1 = [1 for i in range(w-b)]
for i in  range(len(point1)):
    yoko = b+i 
    tate = h-a-1
    n = yoko+tate
    r = yoko
    point1[i] = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod

#point1からの経路
out = 0
for i in range(len(point1)):
    yoko = w-b-i-1
    tate = a-1
    n = yoko+tate
    r = yoko
    case = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod
    out += (point1[i]*case)%mod
print(out%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 23 17:33:45 2019
ABC042D
@author: maezawa
"""

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

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

# 二項係数計算
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 HCOM(n,k):
    return COM(n+k-1,k)


#n, r = list(map(int, input().split()))
#ans = COM(n, r)
#print(ans)

h, w, a, b = list(map(int, input().split()))
cnt = 0
for i in range(h-a):
    p0 = HCOM(b, i) * HCOM(w-b,h-i-1)
    cnt = (cnt+p0)%MOD
print(cnt)

Submission status: Accepted

Solution code:
inp=input().split(" ")
H=int(inp[0])
W=int(inp[1])
A=int(inp[2])
B=int(inp[3])
mod=10**9+7
fact=[1]
fact_r=[1]
for i in range(1,H+W-1):
    fact.append(i*fact[i-1]%mod)
    fact_r.append(pow(fact[i],10**9+5,mod))
const=fact_r[H-A-1]*fact_r[A-1]%mod
ans=sum(fact[H+i-A-1]*fact_r[i]*fact_r[W-i-1]*fact[W-i-2+A]%mod for i in range(B,W))
print(ans*const%mod)