Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

 1 ≦ H, W ≦ 100,000

 1 ≦ A < H

 1 ≦ B < W

Input

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

H W A B

Output

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

Sample Input 1

2 3 1 1

Sample Output 1

2

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

Sample Input 2

10 7 3 4

Sample Output 2

3570

There are 12 forbidden cells.

Sample Input 3

100000 100000 99999 99999

Sample Output 3

1

Sample Input 4

100000 100000 44444 55555

Sample Output 4

738162020



Sample input:
2 3 1 1


Sample output:
2

Submission status: Accepted

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

fac = [1] * (H + W + 1)
x = 1
for i in range(1, H + W + 1):
    x *= i
    x %= p
    fac[i] = x

ifac = [1] * (H + W + 1)
x = fac[H + W]
q = p - 2

while q > 0:
    if q & 1:
        ifac[H + W] *= x % p
    x *= x % p
    q >>= 1

for i in range(H + W - 1, 0, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % p

def com(a, b):
    return (fac[a] * ifac[b] * ifac[a-b]) % p

ans = 0

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

print(ans)

Submission status: Accepted

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


def inv(k):
    return pow(k, M - 2, M)


def comb(n, k):
    if n < k:
        return 0
    elif k == 0:
        return 1
    else:
        r = 1
        for i in range(k):
            r = (r * ((n - i) * inv(k - i)) % M) % M
        return r


ans = comb(h + w - 2, h - 1)

if a == 1 and b == 1:
    ans -= 1
elif a == 1:
    ans -= comb(h + b - 2, h - 1)
elif b == 1:
    ans -= comb(w + a - 2, w - 1)
else:

    memo = [1] * b
    for i in range(1, b):
        memo[i] = (memo[i - 1] * (h - a + i) * inv(i)) % M

    memo2 = [0] * b
    height = a - 1
    width = w - b
    memo2[b - 1] = comb(height + width, height)
    for i in range(1, b):
        memo2[b - i - 1] = (memo2[b - i] * (height + width + i) * inv(width + i)) % M

    ans -= memo[0] * memo2[0]
    ans %= M
    for i in range(1, b):
        ans -= (memo[i] - memo[i - 1]) * memo2[i]
        ans %= M

print(ans % M)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
f = [1] * 300005
for i in range(2, 300005):
    f[i] = (f[i - 1] * i) % MOD

def comb(k, n):
    if n < k:
        return 0
    if k == 0 or n == k:
        return 1
    return (f[n] * pow(f[k], MOD - 2, MOD) * pow(f[n - k], MOD - 2, MOD)) % MOD

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

Submission status: Accepted

Solution code:
mod = 10**9 + 7
N = 200000
fact = [None] * (N+1)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i % mod

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

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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, A, B = list(map(int, sys.stdin.readline().split()))


# dp = np.ones(W, dtype=int)
# for h in range(1, H - A):
#     dp = dp.cumsum() % MOD
# for h in range(H - A, H):
#     dp[B:] = dp[B:].cumsum() % MOD
# print(dp[-1])


def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    :return:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret

def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


factorials = get_factorials(H + W, MOD)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    return factorials[n] * mod_inv(factorials[r], mod) * mod_inv(factorials[n - r], mod) % mod


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

Submission status: Accepted

Solution code:
mod = 1000000007
H, W, A, B = map(int, raw_input().split())

factorial = [1]
for n in xrange(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] * (H+W)
inverseFactorial[H+W-1] = power(factorial[H+W-1], mod-2)
for n in xrange(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 xrange(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 = 10**9+7
fac = [1]
for n in range(1, h+w):
	fac.append(fac[n-1]*n%mod)

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

invfac = [0] * (h+w)
invfac[h+w-1] = modpow(fac[h+w-1], mod-2, mod)
for n in range(h+w-2, -1, -1):
	invfac[n] = invfac[n+1] * (n+1) % mod

def com(a,b):
	return fac[a] * invfac[b] * invfac[a-b] % mod

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

print(r)

Submission status: Accepted

Solution code:
def mf(num,mod):
  ret=1
  for i in range(1,num+1):
    ret=(ret*i)%mod
  return ret

def rev(num,pow,mod):
  ret=1
  while pow>0:
    if pow&1!=0:
      ret=(ret*num)%mod
    pow=pow>>1
    num=(num*num)%mod
  return ret

h,w,a,b=map(int,input().split())
mod=10**9+7
ans=[]
s=0
tb=rev(mf(b,mod),mod-2,mod)
tf=mf(b-1,mod)
trev=[rev(mf(h-a-1,mod),mod-2,mod)]
for i in range(h-a-1,0,-1):
  trev.append((trev[h-a-1-i]*i)%mod)
trev=trev[::-1]
for i in range(h-a):
  tf=(tf*(b+i))%mod
  ans.append((tf*tb*trev[i])%mod)
  ans[i]=(ans[i]-s)%mod
  s+=ans[i]
tb=rev(mf(w-b-1,mod),mod-2,mod)
tf=mf(w+a-b-2,mod)
trev=[rev(mf(h-1,mod),mod-2,mod)]
for i in range(h-1,0,-1):
  trev.append((trev[h-1-i]*i)%mod)
for i in range(h-a-1,-1,-1):
  tf=(tf*(w-b-1+h-i-1))%mod
  ans[i]=(ans[i]*(tf*tb*trev[i])%mod)
ret=0
for i in range(h-a):
  ret+=ans[i]
  ret=ret%mod
print(ret)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX = int(2e5+1)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    i = H-A-1
    j = B
    while i >= 0 and j < W:
        a = (FACT[i+j] * INV[i] * INV[j]) % MOD
        b = (FACT[H-i-1 + W-j-1] * INV[H-i-1] * INV[W-j-1]) % MOD
        ans = (ans + a * b) % MOD
        i -= 1
        j += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, H + W + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


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

Submission status: Accepted

Solution code:
def main():
	H, W, A, B = map(int, input().split())
	H, W= H-1, W-1
	DIV = 10**9+7
	size = H+W+1

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

	for i in range(2, size):
		fact[i] = (fact[i-1]*i%DIV)
		inv_cal[i] = (-inv_cal[DIV%i]*(DIV//i))%DIV
		inverse[i] = inverse[i-1]*inv_cal[i]%DIV

	def C(n, r):
		ans = fact[n]*inverse[r]%DIV
		return ans*inverse[n-r]%DIV

	ans = 0
	for x in range(B, W+1):
		y = H-A
		tmp = (C(x+y, x)*C(H+W-x-y-1, W-x))%DIV
		ans += tmp
		ans %= DIV

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
	H, W, A, B = map(int, input().split())
	H, W= H-1, W-1
	DIV = 10**9+7
	size = H+W+1

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

	for i in range(2, size):
		fact[i] = (fact[i-1]*i%DIV)
		inv_cal[i] = (-inv_cal[DIV%i]*(DIV//i))%DIV
		inverse[i] = inverse[i-1]*inv_cal[i]%DIV

	def C(n, r):
		ans = fact[n]*inverse[r]%DIV
		return ans*inverse[n-r]%DIV

	ans = 0
	for x in range(B, W+1):
		y = H-A
		tmp = (C(x+y, x)%DIV)*(C(H+W-x-y-1, W-x)%DIV)%DIV
		ans += tmp
		ans %= DIV

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def cmb(a, b, fact, mod):
    return fact[a] * pow(fact[b], mod - 2, mod) * pow(fact[a - b], mod - 2, mod) % mod


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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9 + 7
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
 
size = H+ W + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

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

Submission status: Accepted

Solution code:
class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

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

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
INF=10**9+7
x=[0]*(H+W-1)
x[0]=1
for i in range(1,H+W-1):
    x[i]=(i*x[i-1])%INF
y=[0]*(H+W-1)
y[-1]=pow(x[-1],10**9+5,INF)
for i in range(H+W-2,0,-1):
    y[i-1]=(y[i]*i)%INF
ans=0
for i in range(B,W):
    j=H-A-1
    ans+=(x[i+j]*y[i]*y[j])*(x[W-1-i+H-2-j]*y[H-2-j]*y[W-1-i])
    ans%=INF
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import operator as op
from functools import reduce

MODULUS = 10**9 + 7

if __name__ == '__main__':
    [h, w, a, b] = map(int, input().split())

    # Taken from https://atcoder.jp/contests/abc042/submissions/3178794 for learning purposes.
    factorial = [0] * (h+w)
    factorial[0] = 1
    factorial[1] = 1
    inverse = [0] * (h+w)
    inverse[0] = 1
    inverse[1] = 1
    for i in range(2, h+w):
        factorial[i] = factorial[i-1] * i % MODULUS
        # フェルマーの小定理から(x! ** mod-2 % mod == x! ** -1 % mod)
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[i] = pow(factorial[i], MODULUS-2, MODULUS)
        
    # 組み合わせの数だけ返してくれる関数(自作)
    def ncr(n, r):
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = factorial[n]
        # 分母の計算
        denominator = inverse[r] * inverse[n-r] % MODULUS
        return numerator * denominator % MODULUS

    res = 0
    for i in range(h-a):
        rights_and_downs_to_right_border_of_forbidden_area = i + (b-1)

        rights_and_downs_from_right_border_of_forbidden_area = (w - b - 1)  + (h - i - 1) 
        res = (res + ncr( rights_and_downs_to_right_border_of_forbidden_area,   b-1  ) \
            * ncr(  rights_and_downs_from_right_border_of_forbidden_area, (h - i - 1) )) % MODULUS


    print(res)

Submission status: Accepted

Solution code:
H,W,A,B = map(int,input().split())
P=10**9+7
fac=[1]*(H+W)
inv=[1]*(H+W)
finv=[1]*(H+W)
for n in range(2,H+W):
    fac[n]=fac[n-1]*n%P
    inv[n]=(-inv[P%n]*(P//n))%P
    finv[n]=finv[n-1]*inv[n]%P
def comb(n,k):return ((fac[n]*finv[k]%P)*finv[n-k])%P
ans=0
for i in range(1,min(W-B+1,H-A+1)):
    w=B+i-1
    h=H-A-i
    ans=(ans+comb(w+h,w)*comb(W+H-w-h-2,W-w-1))%P
print(ans)

Submission status: Accepted

Solution code:
H,W,A,B=map(int,input().split())
N=H+W+2
mod=10**9+7
table=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
ans=0
for i in range(H-A):
    t=table[B-1+i]*rtable[i]*rtable[B-1]
    s=table[W+H-B-i-2]*rtable[H-i-1]*rtable[W-B-1]
    t=(t*s)%mod
    #print(t)
    ans+=t
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#Combinationクラス
class Combination:

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


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

Submission status: Accepted

Solution code:

def read_input():
    h, w, a, b = map(int, input().split())
    return h, w, a, b


# xの階乗 mod 10**9 + 7 について、1~nまでの結果を辞書にして返す
def factorial_table(n):
    result = {0:1}

    curr = 1
    acc = 1
    modmax = (10**9) + 7
    while curr <= n:
        acc *= curr
        acc %= modmax
        result[curr] = acc
        curr += 1

    return result


# xの逆元 mod 10**9 + 7を求める
def reverse_mod(x):
    return power_n(x, 10**9 + 5)


# xのn乗 mod 10**9 + 7を求める
def power_n(x, n):
    r = 1
    curr_a = x
    modmax = (10 ** 9) + 7
    while n:
        if 1 & n:
            r *= curr_a
            r %= modmax

        n = n >> 1
        curr_a *= curr_a
        curr_a %= modmax

    return r


def comb(x, y, factorial_dic):
    return factorial_dic[x] * reverse_mod(factorial_dic[y]) * reverse_mod(factorial_dic[x - y])


def path(s, e, factorial_dic, modmax):
    x = e[0] - s[0]
    y = e[1] - s[1]

    return comb(x + y, x, factorial_dic) % modmax


def submit():
    h, w, a, b = read_input()
    f_dic = factorial_table(h + w - 2)
    count = 0
    modmax = 10**9 + 7
    for i in range(h - a):
        count += path((0, 0), (i, b - 1), f_dic, modmax) * path((i, b), (h - 1, w - 1), f_dic, modmax)
        count %= modmax

    print(count)

if __name__ == '__main__':
    submit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import exit
H,W,A,B = [int(n) for n in input().split()]
MOD = 10**9+7
NUM = 2*10**5

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

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

    tmp1 = fact[W-i-1+A-1]
    tmp1 *= factinv[W-i-1]
    tmp1 %= MOD
    tmp1 *= factinv[A-1]
    tmp1 %= MOD
    ans += (tmp0 * tmp1) % MOD
    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 = map(int,input().split())

# はじめてB+1列目に入る瞬間で場合分けして足す

ans = 0
for i in range(H-A):
  # (0,0) to (i,B-1)
  x = comb(B-1+i,i)
  # (i,B) to (H-1,W-1)
  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:
h, w, a, b = [int(item) for item in input().split()]

MOD = 10**9 + 7
n = h + w 
def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * mod_pow(i, MOD-2) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

if a+b > (h+w)//2:
    ans = 0
    for i in range(h-a):
        ans += mod_nCr(b-1+i, i) * mod_nCr(w-b-1 + h-1-i, h-1-i)
        ans %= MOD
else:
    ans = mod_nCr(h-1+w-1, h-1)
    for i in range(b):
        ans -= mod_nCr(h-a-1+i, i) * mod_nCr(a-1 + w-1-i, a-1)
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys


def comb(n, r, MOD, factrial, fact_inv):
    if n < 0 or r < 0 or n < r:
        return 0
    else:
        return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

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

    n = H + W - 2

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD
    

    ans = 0
    for w in range(B+1, W+1):
        n_a = H - A + w -2
        r_a = w - 1
        a = comb(n_a, r_a, MOD, factrial, fact_inv)

        n_b = A - 1 + W - w
        r_b = A - 1
        b = comb(n_b, r_b, MOD, factrial, fact_inv)

        ans += (a * b) % MOD

    return ans % MOD


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

Submission status: Accepted

Solution code:
from functools import reduce
import math

memo = []
memo_inv = []
MOD = 10**9+7
    
def get_factorial(i):
    return memo[i]

def get_factorial_inv(i):
    return memo_inv[i]

def nCr(n, r):
    return get_factorial(n) * get_factorial_inv(n-r) * get_factorial_inv(r)

def main():
    # 一文字のみを読み込み
    # s = input().rstrip().split(' ')
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 位置文字ずつ標準入力を配列として読み込み
    # s = list(input().rstrip())
    
    slist = input().rstrip().split(' ')
    H = int(slist[0])
    W = int(slist[1])
    A = int(slist[2])
    B = int(slist[3])
    global memo
    memo = [1]*(H+W+1)
    f= 1
    for i in range(1,H+W+1):
        f *=i
        f %=MOD
        memo[i] = f
        
    global memo_inv
    memo_inv = [1]*(H+W+1)
    memo_inv[H+W] = pow(memo[H+W],MOD-2,MOD)
    f_inv = memo_inv[H+W]
    for i in range(H+W-1,0,-1):
        f_inv *= i +1
        f_inv %= MOD
        memo_inv[i] = f_inv
        
    ans = 0
    for i in range(B,W):
        ans += nCr(i+H-A-1,i) * nCr(W-i-1+A-1,A-1)
    print(ans % MOD)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
m=10**9+7
h,w,a,b=map(int,input().split())
d=c=1
for i in range(h-1):
    d=c=c*(w+h-b-2-i)*pow(i+1,m-2,m)%m
for i in range(1,h-a):
    c=c*(b-1+i)*(h-i)*pow(i*(w+h-b-1-i),m-2,m)%m
    d+=c
print(d%m)

Submission status: Accepted

Solution code:
def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def comb(r: int, c: int, mod: int) -> int:
    if c < 0 or r < c:
        raise Exception('invalid r={}, c={}'.format(r, c))
    if c == 0 or c == r:
        return 1
    return (comb(r-1, c-1, mod) + comb(r-1, c, mod)) % mod


# n+1Cr = (n+1)*n!/((n+1-r)!r!) = ((n+1)/(n+1-r)) * (n!/((n-r)!r!))
def iroha_and_grid(H: int, W: int, A: int, B: int) -> int:
    MOD = 10 ** 9 + 7

    c1, c2 = 1, 1

    uH, uW = H - A, B - 1
    r = uH - 1
    for n in range(r, (uH - 1) + (uW - 1) + 1):
        c1 = (c1 * (n + 1) * mod_inv(n + 1 - r, MOD)) % MOD

    lH, lW = A, W - B
    r = lH - 1
    for n in range(r, (lH - 1) + (lW - 1) + 1):
        c2 = (c2 * (n + 1) * mod_inv(n + 1 - r, MOD)) % MOD

    ret = 0
    for w in range(B, W):
        # 上の領域の高さと幅
        uH, uW = H - A, w - 1
        n = (uH - 1) + (uW - 1) + 1
        r = uH - 1
        c1 = (c1 * (n + 1) * mod_inv(n + 1 - r, MOD)) % MOD

        # 下の領域の高さと幅
        lH, lW = A, W - w
        n = (lH - 1) + (lW - 1)
        r = lH - 1
        c2 = (c2 * (n + 1 - r) * mod_inv(n + 1, MOD)) % MOD

        ret = (ret + c1 * c2) % MOD

    return ret


if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    ans = iroha_and_grid(H, W, A, B)
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7
input = stdin.readline

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# arc058_b

# input
H, W, A, B = map(int, input().split())
mod = 1000000007
# fermat
N = 0
fac = [1]
inv = [1]

def mypow(a, b):
    return _mypow(a, a, b)

def _mypow(p, a, b):
    if b == 1:
        return p
    n = (p*p) % mod
    c, r = divmod(b, 2)
    if r == 0:
        return _mypow(n, a, c)
    else:
        ret = _mypow(n, a, c) * p
        return ret % mod

def init_cmb(_N):
    global N, fac, inv
    N=_N
    fac = [1]
    for i in range(1, N+1):
        n = (fac[i-1] * i) % mod
        fac.append(n)
    inv = (N+1) * [1]
    inv[N] = mypow(fac[N], mod-2)
    for i in range(1, N)[::-1]:
        inv[i] = (inv[i+1] * (i+1)) % mod

def cmb(n, r):
    if (r<0 or n<r): raise Exception(n, r)
    if n>N: raise Exception(n)
    ret = fac[n] * inv[r] * inv[n-r]
    return ret % mod
init_cmb(100000*2)
# getans
def calc(h, w):
    h += -1
    w += -1
    return cmb(h+w, h)
ans = 0
for y in range(1, H-A+1):
    left = calc(y, B)
    right = calc((H-y+1), (W-B))
    ans += left*right
    ans %= mod
# output
print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = list(map(int, input().split()))
 
# 事前計算 + 演算ごとに mod する
def solve():
    # 組合せの計算用に階乗を事前計算しておく
    MOD = 10 ** 9 + 7
    FACT = [0] * (H + W + 1)
    INV_FACT = [0] * (H + W + 1)  # 逆元. 組合せの計算ごとにMODを取るため
 
    FACT[0], INV_FACT[0] = 1, 1
    for i in range(1, (H + W + 1)):
        FACT[i] = (FACT[i - 1] * i) % MOD
        INV_FACT[i] = pow(FACT[i], MOD - 2, MOD)  # フェルマーの小定理を使う
 
    def mod_nCr(n, r):
        if n < r or n == 0 or r == 0:
            return 1
 
        return FACT[n] * (INV_FACT[r] * INV_FACT[n - r]) % MOD
 
    # print(H, W, A, B)
 
    # 座標は(x, y). startは(0, 0)
    goal = W - 1, H - 1
 
    # 境界点: 移動できないエリアの右上の点
    nx = B - 1
    ny = H - A
 
    # 境界点から右斜め上に1つ移動した点(choke_left)から, 右端へ伸びる線がchoke points
    choke_left = nx + 1, ny - 1
 
    choke_points = []
    for i in range(B, W):
        choke_points.append((i, choke_left[1]))
 
    # 組合せを計算する: startからcp1, cp2からgoalまで組合せを掛ける
    ans = 0
    for cp1 in choke_points:
        x, y = cp1
        from_start_to_cp1 = mod_nCr(x + y, x)
 
        # cp1から1つ下の点がcp2
        y += 1
        dx, dy = goal[0] - x, goal[1] - y
        from_cp2_to_goal = mod_nCr(dx + dy, dx)
 
        ans = ans % MOD + (from_start_to_cp1 * from_cp2_to_goal % MOD) % MOD
 
    return ans % MOD
 
res = solve()
print(res)

Submission status: Accepted

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

factorial = [1]
inv_factorial = [1]


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


def f(h, w):
    return (factorial[h+w-2] * inv_factorial[h-1] * inv_factorial[w-1]) % MOD


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

print(int(answer))

Submission status: Accepted

Solution code:
# coding: UTF-8
import numpy as np

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

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

ifact = [pow(fact[-1], MOD-2, MOD)]
for i in reversed(range(1, W+H-1)):
    ifact.append((ifact[-1]*i) % MOD)
ifact.reverse()


def comb(n, r):
    return fact[n]*ifact[n-r]*ifact[r]


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

print(int(s))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import bisect
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

class comb_calclator():
    def __init__(self, N, p):
        self.N = N
        self.p = p
        self.frac_N = [0 for i in range(N + 1)]
        self.frac_N[0] = 1L
        self.comb_N = {}
        for i in range(1, N + 1):
            self.frac_N[i] = (self.frac_N[i - 1] * i ) % p

    def comb(self, n, r):
        if n<0 or r<0 or n<r: return 0
        if n==0 or r==0: return 1
        if (n, r) in self.comb_N:
            return self.comb_N[(n, r)]
        a = self.frac_N[n]
        b = self.frac_N[r]
        c = self.frac_N[n - r]
        self.comb_N[(n, r)] = (a*power_func(b,self.p-2,self.p)*power_func(c,self.p-2, self.p))% self.p
        self.comb_N[(n, n - r)] = self.comb_N[(n, r)]
        return self.comb_N[(n, r)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, A, B] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2]), int(input_raw[3])]
    p = 1000000007
    cmb = comb_calclator(H + W, p)
    count = 0L
    for i in range(H - A):
        count = (count + cmb.comb(B - 1 + i, i) * cmb.comb((W - B - 1) + (H - 1) - i, (H - 1) - i)) % 1000000007

    print count

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class ModCmb:
    def __init__(self, size):
        self.inv = [1] * (size + 1)
        self.fact = [1] * (size + 1)
        temp_inv = [1] * (size + 1)
        for i in range(2, size + 1):
            temp_inv[i] = ( -(MOD // i) * temp_inv[MOD%i] ) % MOD
        for i in range(2, size + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
            self.inv[i] = self.inv[i-1] * temp_inv[i] % MOD

    def cmb(self, n, r):
        #print(n, r)
        if n <= 1 or n == r:
            return 1
        elif r == 1:
            return n
        res = (self.fact[n] * self.inv[r] % MOD ) * self.inv[n-r] % MOD
        #print(res)
        return res

c = ModCmb(h+w)

ans = 0
x = h-a-1
y = w-b-1
for i in range(h-a):
    j = h+w-2-i-b
    #print(i, j)
    #print(i+b-1, b-1, j, w-b-1)
    ans += c.cmb(i+b-1, b-1) * c.cmb(j, w-b-1)
    ans %= MOD

print(ans % MOD)