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:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    
######################################################

#nCk mod p
def mod_comb(n,k):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
######################################################

h,w,a,b = map(int,input().split())
#pは素数とする
p = 10**9+7
#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,10**6+10):
    k = k*i%p
    fact.append(k)

res = 0
for i in range(h-a):
    res += mod_comb(i+b-1,b-1)*mod_comb(h-i-1+w-b-1,w-b-1)
    res = res%p
print(res)

Submission status: Accepted

Solution code:
mod = 10**9+7


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


class Fact():
    def __init__(self, H, W):
        self.mod = 10**9+7
        self.facts = [1]*(H+W-1)
        for i in range(1, H+W-1):
            self.facts[i] = self.facts[i-1]*i % mod

        self.i = [pow(self.facts[-1], mod-2, mod)]
        for i in range(1, H+W-1)[::-1]:
            self.i.append(self.i[-1]*i % mod)
        self.i.reverse()

    def comb(self, n, r):
        ret = self.facts[n] * self.i[n-r]*self.i[r]
        return ret

    def print_fact(self):
        print(self.facts)


f = Fact(H, W)

all_path = f.comb(H+W-2, H-1)

remove_path = 0
for i in range(B):
    tmp = f.comb(H-A+i-1, i)
    tmp *= f.comb(W-i-1+A-1, A-1)
    remove_path += tmp

remove_path %= mod

print((all_path - remove_path) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 1000000007
H, W, A, B = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
factorial = [1]
for n in range(1, H+W):
    factorial.append(factorial[n-1]*n % mod)

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

def combi(n, m):
    return (factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] )% mod
 
sum = 0
for i in range(B+1, W+1):
    sum = (sum + combi(H-A-1+i-1, i-1) * combi(A-1+W-i, W-i)) % mod
print(sum)

Submission status: Accepted

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

def Power(i, n):
    if n == 1:
        return i
    else:
        if n%2 == 0:
            return Power((i*i)%mod, n//2)
        else:
            return (Power((i*i)%mod, n//2) * i) % mod

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

NFI = [1 for i in range(H+W+1)]
NFI[H+W] = Power(NF[-1], mod-2)
for i in reversed(range(1, H+W)):
    NFI[i] = (NFI[i+1] * (i+1)) % mod

Ans = 0
for w in range(B, W):
    upper = (NF[H-A+w-1] * NFI[w] * NFI[H-A-1]) % mod
    lower = (NF[W+A-w-2] * NFI[A-1] * NFI[W-w-1]) % mod
    Ans += upper * lower % mod
    Ans %= mod
print(Ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

mod = 10**9+7
H, W, A, B = inpl()
fac = [1 for _ in range(H+W-1)]
for i in range(H+W-2):
    fac[i+1] = (i+1)*fac[i]%mod

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

facinv = [1 for _ in range(H+W-1)]
for i in range(H+W-2):
    facinv[i+1] = inv[i+1]*facinv[i]%mod


ans = 0
for i in range(W-B):
    ans += (fac[H+B-A-1+i] * fac[W+A-B-2-i] * facinv[H-A-1] * facinv[B+i]\
    * facinv[A-1] * facinv[W-B-1-i] )%mod
print(ans%mod)

Submission status: Accepted

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

u = {}
for i in range(B, W):
    t = fact[i + H - A - 1] * pow(fact[i] * fact[H - A - 1], MOD - 2, MOD)
    u[i + 1] = t % MOD

ans = 0
for k, v in u.items():
    t = fact[W - k + A - 1] * pow(fact[W - k] * fact[A - 1], MOD - 2, MOD) % MOD
    ans = (ans + t * v) % MOD

print(ans)

Submission status: Accepted

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

MOD = 1000000007
fact = []

def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)

def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, min(dx, dy))
    return count

def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li

def combi(n, k):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % MOD
    return (numera * inv(denomi)) % MOD

def init_fact(maxn):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % MOD)

def inv(n):
    return pow(n, MOD - 2)

def pow(n, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2)
        return (x * x) % MOD
    else:
        x = pow(n, p - 1)
        return (x * n) % MOD

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
 
import functools
 
MOD = 1000000007
fact = []
 
def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)
 
def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count
 
def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li
 
def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod
 
def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)
 
def inv(n, mod):
    return pow(n, mod - 2, mod)
 
def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod
 
main()

Submission status: Accepted

Solution code:
ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2
ans %= mod

for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) * inv(b + i) % mod
    c2 = c2 * (bb - i + 1) * inv(a + bb - i) % mod
    ans += c1 * c2
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
MOD = 10**9 + 7
c1 = []
c2 = []
for i in range(H-A):
    if i == 0:
        c1.append(1)
        c2.append(1)
    else:
        m = pow(i, MOD-2, MOD)
        t1 = (c1[i-1]*(B-1+i) % MOD) * m
        c1.append(t1 % MOD)
        t2 = (c2[i-1]*(W-B-1+i) % MOD) * m
        c2.append(t2 % MOD)
for i in range(H-A, H):
    t = (c2[i-1]*(W-B-1+i) % MOD) * pow(i, MOD-2, MOD)
    c2.append(t % MOD)
ans = 0
for i in range(len(c1)):
    ans += (c1[i]*c2[-i-1]) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import math
mod = 10**9+7
def inv(x):
	return pow(x,mod-2,mod)


MAX = 10**5*3
facts = [1 for i in range(MAX)]
invs = [1 for i in range(MAX)]


def factorial(x):
	for i in range(1,x):
		facts[i] = (facts[i-1] * i)% mod
		invs[i] = inv(facts[i])

factorial(MAX)
def nCr(n,r):
	return facts[n]*invs[r] * invs[n-r] % mod

h,w,th,ty = map(int,raw_input().split())

ans = 0

for i in range(ty+1,w+1):
	
	ans += (nCr(h-th-1 + i-1,i-1)%mod * nCr(th-1 + w-i,w-i)%mod)%mod

print ans%mod

Submission status: Accepted

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

M, S = 10 ** 9 + 7, H + W - 2
fact_n = [0 for i in range(S+1)]
fact_inv = [0 for j in range(S+1)]


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    res = fact_n[n] * fact_inv[r] % M
    return res * fact_inv[n-r] % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, S+1):
        fact_n[i] = fact_n[i-1] * i % M

    fact_inv[S] = pow(fact_n[S], M-2, M)
    for i in range(S-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

    com, bef = combination(S, H-1), 0
    for i in range(B):
        c1, c2 = combination(H-A+i, H-A), combination(S-H+A-i, A-1)
        tmp = (c1-bef) * c2 % M
        bef += c1 - bef
        com -= tmp
        if com < 0:
            com += M

    print(com)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

# inv[k]: kの逆元
N = H - 1
inv = [0] * (N + 1)
inv[1] = 1
for k in range(2, N + 1):
    inv[k] = (-(MOD // k) * inv[MOD % k]) % MOD

# C1s[i]: 左上のマス目から、「左からB個目・上からi個目のマス目」まで移動する場合の数
n1 = B - 1
C1s = [0] * (H - A)
C1s[0] = 1
for r in range(1, H - A):
    C1s[r] = (C1s[r - 1] * (n1 + r) * inv[r]) % MOD

# C2s[i]: 「左から(B+1)個目・下からi個目のマス目」から、右下のマス目まで移動する場合の数
n2 = W - B - 1
C2s = [0] * H
C2s[0] = 1
for r in range(1, H):
    C2s[r] = (C2s[r - 1] * (n2 + r) * inv[r]) % MOD

ans = 0
for i in range(H - A):
    ans += (C1s[i] * C2s[- 1 - i]) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
h, w, a, b = map(int, raw_input().split())
p = 10 ** 9 + 7
z = 0
s = 1
for i in range(w - b - 1):
	s = s * (h + w - b - 2 - i) * pow(i + 1, p - 2, p) % p
for i in range(h - a):
	z = (z + s) % p
	s = s * (b + i) * (h - 1 - i) * pow((i + 1) * (h + w - b - 2 - i), p - 2, p) % p
print z

Submission status: Accepted

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

count = 0

factoriallist = [1]*(H+W)
for i in range(1,H+W):
    factoriallist[i] = factoriallist[i-1]*i % mod
#print("fact",factoriallist)

inverse_factoriallist = [0]*(H+W)
inverse_factoriallist[H+W-1] = pow(factoriallist[H+W-1],mod-2,mod)
#print("inverse",inverse_factoriallist)
for i in range(H+W-2,-1,-1):
    
    inverse_factoriallist[i] = inverse_factoriallist[i+1] * (i+1) % mod
    #print("inverse",inverse_factoriallist)


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

print(int(count% mod))

Submission status: Accepted

Solution code:
M = 1000000007
H,W,A,B = map(int,input().split())
factorial_list = [0] * (H+W)
factorial_list[0] = 1
for i in range(1,H+W):
    factorial_list[i] = factorial_list[i-1]*i %M
inverse_factorial_list = [0] * (H+W)

def power(a,n):
    if n == 0:
        return 1
    if n == 1:
        return a % M
    if n % 2 == 0:
        return power(a,n//2)**2 % M
    return (power(a,n-1) * a) % M

inverse_factorial_list[H+W-1] = power(factorial_list[H+W-1],M-2)
for i in range(H+W-2,-1,-1):
    inverse_factorial_list[i] = inverse_factorial_list[i+1] *(i+1) %M

def C(a,b):
    return factorial_list[a+b] * inverse_factorial_list[a] * inverse_factorial_list[b] % M
    
route = 0
for i in range(B,W):
    a = H - A - 1
    b =  i
    c = A - 1
    d = W - i - 1
    route += ((C(a,b)%M) * (C(c,d)%M)) 
    route %= M

print(route)

Submission status: Accepted

Solution code:
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
H,W,A,B=map(int,input().split())
N=H+W
fact=[0 for i in range(N+1)]
finv=[0 for i in range(N+1)]
fact[0]=1
finv[0]=1
for i in range(1,N+1):
    fact[i]=(fact[i-1]*i)%P
    finv[i]=(inv(fact[i]))%P
def C(a,b):
    return (fact[a+b]*(finv[a]*finv[b])%P)%P
D=0
for i in range(B,W):
    K=(C(H-A-1,i)*C(A-1,W-1-i))%P
    D=(D+K)%P
print(D)
'''
HWAB
6734
4   C(2,4)*C(2,2)   15*6=90
5   C(2,5)*C(2,1)   21*3=63
6   C(2,6)*C(2,0)   28*1=28

'''

Submission status: Accepted

Solution code:
BIG = (10 ** 9) + 7

f_list = [1] * 200000
f_r_list = [1] * 200000

for i in range(199999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % BIG)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % BIG), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % BIG)

f_r_list[-1] = power(f_list[-1], BIG - 2)

for i in range(2, 200001):
	f_r_list[-i] = int((f_r_list[-i + 1] * (200002 - i)) % BIG)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % BIG) * f_r_list[r - 1]) % BIG 

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

ans = 0

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

print(int(ans))

Submission status: Accepted

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

# nCr mod P (P は素数) を 1 <= r <= n <= N の範囲で求めるための前処理の関数
# fact は n! mod P (n=0,...,N) のリストを返す
# inv_fact は n!^(-1) mod P (n=0,...,N) のリストを返す
def fact(N, P):
    ret = [1] * (N + 1)
    for n in range(2, N+1):
        ret[n] = (ret[n-1] * n) % P

    return ret


# 二分累乗法による a ** b mod P の計算
def pow_r(a, b, P):
    """
    O(log n)
    """
    if b == 0:  # exit case
        return 1
    if b % 2 == 0:  # standard case ① n is even
        return pow_r((a ** 2) % P, b // 2, P)
    else:  # standard case ② n is odd
        return (a * pow_r((a ** 2) % P, (b - 1) // 2, P)) % P


def inv_fact(N, P):
    ret = [1] * (N + 1)
    fac = fact(N, P)
    ret[N] = pow_r(fac[N], P - 2, P)
    for n in reversed(range(2, N)):
        ret[n] = (ret[n + 1] * (n + 1)) % P

    return ret


fac = fact(N, P)
inv = inv_fact(N, P)
# nCr mod P (P は素数) を 1 <= r <= n <= N の範囲で求める関数
def combination(n, r, P):
    return (fac[n] * inv[r] * inv[n - r]) % P



sub = 0
for a in range(A):
    sub = (sub + combination((H - 1 - a) + (B - 1), B - 1, P) * combination(a + (W - 1 - B), a, P)) % P

print((combination((H - 1) + (W - 1), H - 1, P) - sub) % P)

Submission status: Accepted

Solution code:
h,w,a,b=[int(x)for x in raw_input().split()]
m=1000000007
def f(*n):
 r=1
 for i in xrange(*n):r=r*(i+1)%m
 return r
def g(n):return pow(n,m-2,m)
c=s=f(w-b-1,h+w-b-2)*g(f(h-1))%m
for i in xrange(1,h-a):
 s=s*(b+i-1)%m*(h-i)%m*g(i*(h+w-b-1-i)%m)%m
 c=(c+s)%m
print c

Submission status: Accepted

Solution code:
MOD=10**9+7
fact=[1 for i in range(200010)]
ifact=[1 for i in range(200010)]
for i in range(2,200010):
    fact[i]=(fact[i-1]*i)%MOD
    ifact[i]=(ifact[i-1]*pow(i,MOD-2,MOD))%MOD
def nCm(n,m):
    global MOD,fact,ifact
    return (fact[n]*((ifact[m]*ifact[n-m])%MOD))%MOD
h,w,a,b=map(int,input().split())
ret=0
for i in range(h-a):
    ret+=(nCm(i+b-1,i)*nCm((h-i-1)+(w-b-1),h-i-1))%MOD
    ret%=MOD
print(ret)

Submission status: Accepted

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

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

fct = [1]
inv = [1]
for i in range(1, H + W - 1):
    fct.append((fct[-1] * i) % mod)
    inv.append(pow(fct[i], mod - 2, mod))

def comb(n, k):
    return (fct[n] * inv[n - k] * inv[k]) % mod

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

Submission status: Accepted

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

mod = 10**9 + 7

def inv(x):
    return pow(x, mod - 2, mod)

def comb(n, k):
    res = 1
    for i in range(k):
        res = (res * (n - i) * inv(i + 1)) % mod
    return res

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

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

Submission status: Accepted

Solution code:
MOD = 1000000007
kaijo = []
kaijo_1 = []

def power(a, n):
    if (n == 0):
        return 1
    res = 1
    while (n > 0):
        if ((n & 1) == 1):
            res = res * a % MOD
        a = a * a % MOD
        n >>= 1
    
    return res    

def calcKaijo():
    kaijo.append(1)
    for i in range(1, 200001):
        kaijo.append((kaijo[i - 1] * i) % MOD)

def calcKaijo_1():
    for i in range(200001):
        kaijo_1.append(0)
    kaijo_1[200000] = power(kaijo[i], MOD - 2)
    for i in range(199999, -1, -1):
        kaijo_1[i] = kaijo_1[i + 1] * (i + 1) % MOD

def comb(n, r):
    return kaijo[n] * kaijo_1[n - r] * kaijo_1[r]

calcKaijo()
calcKaijo_1()
h, w, a, b = [int(i) for i in input().split()]
count = 0
for i in range(b, w):
    count += comb(h - a - 1 + i, i) * comb(a - 1 + w - 1 - i, w - 1 - i)
    count %= MOD

print(count)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def inv(x):
    return pow(x, mod - 2, mod)

def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod

def main():
    h,w,a,b = LI()
    c1 = nCb(h-a-1+b, b)
    c2 = nCb(w-b-1+a, a)
    r = 0
    for i in range(1, min(h-a, w-b)+1):
        r += c1 * c2
        r %= mod
        c1 = c1 * (h-a-i) * inv(b+i) % mod
        c2 = c2 * (w-b-i) * inv(a+i) % mod

    return r

print(main())

Submission status: Accepted

Solution code:
import scipy.misc as scm

H, W, A, B = [int(i) for i in input().split()]
MOD = 10**9 + 7
f = [1]
a = [1]
for i in range(1, H+W-1):
    f.append((f[i-1] * i) % MOD)
    a.append(pow(f[i], MOD-2, MOD))
ans = 0
for i in range(B, W, 1):
    ans += (((f[(H-A-1)+i] * a[H-A-1] * a[i]) % MOD) * ((f[(A-1)+(W-1-i)] * a[A-1] * a[W-1-i]) % MOD))
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, stdout, stderr

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = map(int, input().split())
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)
    inv = [1] * (h + w)

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

    factinv[h + w - 1] = pow(modfact[h + w - 1], mod - 2, mod)

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

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

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin, stdout, stderr

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = map(int, input().split())
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)
    inv = [1] * (h + w)

    for i in range(2, h + w):
        modfact[i] = (i * modfact[i - 1]) % mod
        inv[i] = (-(mod // i) * inv[mod % i]) % mod
        factinv[i] = (inv[i] * factinv[i - 1]) % mod

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

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin, stdout, stderr, setrecursionlimit
from functools import lru_cache

setrecursionlimit(10**7)

mod = 10**9 + 7

def solve():
    def binom(n, k):
        res = (modfact[n] * factinv[k]) % mod
        res = (res * factinv[n - k]) % mod
        return res

    h, w, a, b = map(int, input().split())
    ans = 0
    modfact = [1] * (h + w)
    factinv = [1] * (h + w)

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

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

    print(ans)

'''
@lru_cache(maxsize=None)
def binom(n, k):
    res = (modfact(n) * factinv(k)) % mod
    res = (res * factinv(n - k)) % mod
    return res

@lru_cache(maxsize=None)
def modfact(n):
    if n == 0:
        return 1

    return (n * modfact(n - 1)) % mod

@lru_cache(maxsize=None)
def factinv(n):
    if n == 0:
        return 1

    return (pow(n, mod - 2, mod) * factinv(n - 1)) % mod
'''

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

MOD = 10**9+7

M = 2*10**5
fact = [1]*(M+1)
rev = [1]*(M+1)
for i in xrange(1, M+1):
    fact[i] = (fact[i-1]*i) % MOD
    rev[i] = pow(fact[i], MOD-2, MOD)

def comb(a, b):
    a -= 1; b -= 1
    return (fact[a+b] * rev[a] * rev[b]) % MOD

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

Submission status: Accepted

Solution code:
p = 10**9+7; M=10**5;
F = [1]; FI=[0]*(M+1)
for i in xrange(1,M*2+1):F+=[i*F[i-1]%p]
FI[M]=pow(F[M],p-2,p)
for i in xrange(M,0,-1):FI[i-1]=i*FI[i]%p
H,W,A,B = map(int,raw_input().split())
hx,hy = B+1,H-A
ans = 0
while hx <= W and hy > 0:
	tmp = F[hx+hy-2]*FI[hx-1]*FI[hy-1]%p * F[W-hx+H-hy]*FI[W-hx]*FI[H-hy]%p
	ans = (ans + tmp) % p
	hx += 1; hy -= 1
print ans

Submission status: Accepted

Solution code:
import functools

MOD = 1000000007

fact = [None] * 300000
fact[0] = 1
for i in range(1, 300000):
    fact[i] = (i * fact[i - 1]) % MOD

def comb(h, w):
    numer = fact[h - 1 + w - 1]
    denom = (fact[h - 1] * fact[w - 1]) % MOD
    # print('numer, denom =', numer, denom)

    return (numer * pow(denom, MOD - 2, MOD)) % MOD

H, W, A, B = map(int, input().split())
ans = 0
for h in range(H - A):
    x = comb(h + 1, B)
    y = comb(H - h, W - B)
    # print(x, y)
    ans += x * y
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from sys import exit
from itertools import count

def read():
  return [int(x) for x in input().split()]

P = 10**9 + 7

def inv(x):
  return pow(x, P-2, P)

def comb(n, r):
  res = 1
  for i in range(r):
    res = (res * (n-i) * inv(i+1)) % P
  return res

(H, W, A, B) = read()

result = 0

c1 = comb(H-A-1+B, B)
c2 = comb(W-B-1+A, A)

for i in range(1, min(H-A+1, W-B+1)):
  # print(c1, c2)
  result = (result + c1 * c2) % P
  c1 = (c1 * (H-A-i) * inv(B+i)) % P
  c2 = (c2 * (W-B-i) * inv(A+i)) % P

print(result)

Submission status: Accepted

Solution code:
if __file__.startswith('/tmp/'):
	import sys; sys.stdin = open('input.txt')

MOD = 10**9 + 7

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

def inv(x):
	return pow(x, MOD-2, MOD)

x = [1]
y = [1]

for k in xrange(1, h - a):
	x.append(((x[-1] * (b - 1 + k)) % MOD) * inv(k) % MOD)

for k in xrange(1, h):
	y.append(((y[-1] * (w - b - 1 + k)) % MOD) * inv(k) % MOD)

ans = 0
for k in xrange(h - a):
	ans = (ans + x[k] * y[h - k - 1]) % MOD

print ans

Submission status: Accepted

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

fm = [1]
for i in xrange(1, 300000):
    fm.append(fm[-1] * i % mod)

def f(x):
    return fm[x]

def inv(x):
    return pow(x, mod - 2, mod)

def c(x, y):
    return f(x + y) * inv(f(x)) % mod * inv(f(y)) % mod

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

print ans

Submission status: Runtime Error

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 2 * 10 ** 6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = comb(H + W - 2, H - 1)
for x in range(H - A, H):
    ans -= comb(x + B - 1, B - 1) * (H - 1 - x + W - B, W - B)
print(ans)

Submission status: Runtime Error

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 10**6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = 0
for x in range(H - A, H):
    ans += comb(x + B - 1, B - 1) * (H - 1 - x + W - B, W - B)
print(ans)

Submission status: Runtime Error

Solution code:
"""
fast way to compute a combination using inverse factorials
O(N) to construct tables -> O(1) to compute each combination
"""
from typing import List, Tuple


def get_fact(lim: int) -> List[int]:
    """Compute a table of factorials (1-indexed)."""
    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: int) -> List[int]:
    """Compute a table of inverse factorials (1-indexed)."""
    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 get_fact_and_inv(lim: int) -> Tuple[List[int], List[int]]:
    """Compute tables of factorials and inverse factorials (1-indexed)."""
    fact = [0] * (lim + 1)
    fact[0] = 1
    x = 1
    for i in range(1, lim + 1):
        x = (x * i) % MOD
        fact[i] = x

    inv = [1] * (lim + 1)
    inv[-1] = pow(fact[-1], MOD - 2, MOD)
    x = inv[-1]
    for i in range(lim - 1, 0, -1):
        x = (x * (i + 1)) % MOD
        inv[i] = x
    return fact, inv


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


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


if __name__ == "__main__":
    main()