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:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Combination:
    def __init__(self, n, mod):

        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)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

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


@mt
def slv(H, W, A, B):
    MOD = 10**9+7
    cmb = Combination(H+W, MOD)
    ans = 0
    for i in range(W-B):
        w1 = cmb(i+(A-1), i)
        w2 = cmb((W-i-1)+(H-A-1), (H-A-1))
        ans += w1*w2
        ans %= MOD

    return ans % MOD


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

    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


nCr = {}


def C(n, r):
    if r == 0 or r == n:
        return 1
    if r == 1:
        return n
    if (n, r) in nCr:
        return nCr[(n, r)]
    nCr[(n, r)] = C(n-1, r) + C(n-1, r-1)
    return nCr[(n, r)]


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

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


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


@mt
def slv(H, W, A, B):
    MOD = 10**9+7
    ans = 0
    for i in range(W-B):
        # print(ans)
        w1 = cmb(i+(A-1), i)
        w2 = cmb((W-i-1)+(H-A-1), (H-A-1))
        ans += w1*w2
        ans %= MOD

    return ans % MOD


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

    print(slv(H, W, A, B))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

m = 10**9 + 7

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * ic[c] * ic[r] % m

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m
ic = [pow(x, m-2, m) for x in fc]

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)

Submission status: Accepted

Solution code:
# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if n==0 and r==0:
        return 1

    elif not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod


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

inv = inv_mod(H+W, mod)
fac = fact(H+W, mod)
facInv = fact_inv(H+W,inv,mod)

checkPoint = []
for i in range(H-A):
    checkPoint.append((i,B-1))
    
ans = 0
for h,w in checkPoint:
    ans = (ans + nCr(h+w,h,mod,fac,facInv) \
                * nCr(H+W-h-w-3, H-h-1, mod, fac, facInv)) % mod
    
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

fact = [1] * (H + W - 1)
invfact = [1] * (H + W - 1)

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

def nCr(n,r):
    return fact[n] * invfact[r] * invfact[n-r]

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

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
F = [1 for i in range(H + W + 1)]
for i in range(1, H + W + 1):
  F[i] = F[i - 1] * i % p
Fi = [pow(f, p - 2, p) for f in F]
def fac(a, b):
  a = F[a + b] * Fi[a] * Fi[b]
  return a % p
if H - A < B:
  ans = 0
  for h in range(H - A):
    ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
else:
  ans = fac(H - 1, W- 1)
  for w in range(B):
    ans -= fac(H - A - 1, w) * fac(A - 1, W - w - 1) % p
print(ans % p)

Submission status: Accepted

Solution code:
from math import factorial

mod = 10**9 + 7

H, W, A, B = map(int, input().split())
memo_fact = [1] * (H + W - 1)
memo_denometer = {}
for i in range(1, H + W - 1):
    memo_fact[i] = memo_fact[i - 1] * i % mod

def nCr(n,r):
    numerator = memo_fact[n]
    if (n, r) in memo_denometer:
        denometer = memo_denometer[(n, r)]
    else:
        denometer = pow(memo_fact[r], mod-2, mod) * pow(memo_fact[n-r], mod-2, mod)
    return (numerator * denometer) % mod

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

Submission status: Accepted

Solution code:
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

M = H+W-1
factlist = [1] * (H+W)
factinvlist = [1] * (H+W)
t = 1
for i in range(M):
	t = (t * (i+1)) % P
	factlist[i+1] = t
t = pow(factlist[M],P-2,P)
factinvlist[M] = t
for i in range(M):
	t = (t * (M-i)) % P
	factinvlist[M-i-1] = t

def comb(i,j):
	return (factlist[i+j] * factinvlist[i] * factinvlist[j]) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)

Submission status: Accepted

Solution code:
import math
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
F = [1 for i in range(H + W + 1)]
for i in range(1, H + W + 1):
  F[i] = F[i - 1] * i % p
def fac(a, b):
  a = F[a + b] * pow(F[a], p - 2, p) * pow(F[b], p - 2, p)
  return a % p
ans = 0
for h in range(H - A):
  ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
print(ans % p)

Submission status: Accepted

Solution code:
import math
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
F = [1 for i in range(H + W + 1)]
for i in range(1, H + W + 1):
  F[i] = F[i - 1] * i % p
def fac(a, b):
  a = F[a + b] * pow(F[a], p - 2, p) * pow(F[b], p - 2, p)
  return a % p
if H - A < B:
  ans = 0
  for h in range(H - A):
    ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
else:
  ans = fac(H - 1, W- 1)
  for w in range(B):
    ans -= fac(H - A - 1, w) * fac(A - 1, W - w - 1) % p
print(ans % p)

Submission status: Accepted

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

p = 10 ** 9 + 7

ans = 0
c = h-a-1

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(h+w-2)
invf = invfact(h+w-2, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

for x in range(b, w):
    ans = (ans + (comb(c+x, min(x, c)) * comb(a-1+w-x-1, min(a-1, w-x-1)) % p)) % p

print(ans)

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
mod=10**9+7
fuc=[1]
for i in range(1,h+w):
    e=fuc[i-1]*i
    fuc.append(e%mod)

def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com

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

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

facts = [1]
for i in range(1, h+w-1):
    facts.append((i*facts[i-1])%MOD)
# print(facts[:20])
    
def get_path(n, r):
    return (facts[n] * pow(facts[r], MOD-2, MOD)%MOD * pow(facts[n-r], MOD-2, MOD)%MOD) % MOD

y, x = h-a, b+1
while(True):
    path_0 = get_path(y+x-2, x-1)
    path_1 = get_path(h-y+w-x, w-x)
    # print(y, x, path_0, path_1)
    ans += (path_0*path_1)%MOD
    ans %= MOD

    y -= 1
    x += 1
    if y == 0 or x > w:
        break
    
print(ans)

Submission status: Accepted

Solution code:
h, w, a, b = map(int, raw_input().split())
mod = 1000000007
inv = [0] * (h+w)
fact = [0] * (h+w)

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

# factorial
fact[0]=1
for j in range(1, h+w):
    fact[j] = fact[j-1] * j % mod

inv[h+w-1]=ex(fact[h+w-1],mod-2)
for j in reversed(range(h+w-1)):
    inv[j]=inv[j+1]*(j+1)%mod

def nck(x, y):
  return fact[x] * inv[y] * inv[x-y] % mod

su = 0

for j in range(h-a):
  su = (su+nck(b-1+j, b-1)*nck(h-1-j+w-1-b, w-1-b)) % mod

print(su)

Submission status: Accepted

Solution code:
H, W, A, B = (int(i) for i in input().split())

#H, W, A, B = (10, 7, 3, 4)
#H, W, A, B = (2, 3, 1, 1)

def mycomb(n,r):
    return (factorials[n] * pow(factorials[r],MOD-2,MOD) % MOD) * pow(factorials[n-r],MOD-2,MOD) % MOD

MOD = int(1e9 + 7)

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

r = 0
for i in range(H - A):
    combination = mycomb(B-1+i, B-1) * mycomb(W+H-B-i-2, W-B-1)
    r += int(combination)

print(r%MOD)

Submission status: Accepted

Solution code:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


# nCrをすべてのr(0<=r<=n)について求める
def combination(n, mod):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst

H, W, A, B = map(int, input().split())
x, y = B, H-A-1
n1 = x+y
n2 = W+H-n1-2
mod = 10**9+7
C1 = combination(n1, mod)
C2 = combination(n2, mod)
ans = 0
while x<W and y>=0:
    ans += C1[x] * C2[W-x-1]
    ans %= mod
    x += 1
    y -= 1
print(ans)

Submission status: Accepted

Solution code:
def ext_gcd(a,b):
    """returns tuple (gcd(a,b), x, y) s.t. ax+by=gcd(a,b)"""
    if b==0:
        return (a,1,0)
    g,x,y = ext_gcd(b,a%b) 
    return (g,y,x-a//b*y)
def invmod_by_gcd(a,P):
    _,x,y = ext_gcd(a,P)
    return (x+P) % P

F = []
FInv = []

def init_factorials(L,P):
    """initialize F and FInv less than L"""
    global F, FInv
    F = [1 for _ in range(L)]
    for i in range(1,L):
        F[i] = (F[i-1]*i)%P
    FInv = [1 for _ in range(L)]
    FInv[L-1] = invmod_by_gcd(F[L-1],P)
    for i in range(L-2,0,-1):
        FInv[i] = (FInv[i+1]*(i+1))%P
      
def combination(a, b, P):
    return (F[a]*FInv[b]*FInv[a-b])%P

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

init_factorials(H+W,P)

ans = 0
for k in range(H-A):
    a = combination(B+k-1,B-1,P)
    b = combination(H+W-k-B-2,H-1-k,P)
    ans = (ans + a*b%P)%P
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
p = 10**9+7
def power(a,b):
    if b == 0:
        return 1
    elif b%2 == 0:
        return (power(a,b//2)**2)%p
    else:
        return (a*power(a,b//2)**2)%p
def fact(a):
    if a <= 0:
        return 1
    else:
        return (a*fact(a-1))%p
H,W,A,B = map(int,input().strip().split(" "))
a,b = fact(H+B-A-1)%p,fact(W+A-B-1)%p
c,d = H-A-1,W-B-1
m = max(H-1,W-1)
mods = [1]*(m+1)
mods[m] = power(fact(m),p-2)
for i in range(m):
    mods[m-i-1] = (mods[m-i]*(m-i))%p
ans = 0
for i in range(min(c,d)+1):
    ans = (ans+a*b*mods[A+i]*mods[B+i]*mods[c-i]*mods[d-i])%p
print(ans)

Submission status: Accepted

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

fact = [1]*200001
t = 1
for i in range(1,200001):
    t = (t*i)%MOD
    fact[i] = t

def ncr(n,r):
    return (fact[n] * pow(fact[r],MOD-2,MOD) % MOD) * pow(fact[n-r],MOD-2,MOD) % MOD

Ans = 0
for i in range(H-A):
    Ans += ncr(i+B-1,i)*ncr(W-B+H-i-2,W-B-1)

print(Ans%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = 200000
p = [1] * (N+1)
q = [1] * (N+1)
for i in range(1, N+1):
    p[i] = (p[i-1]*(i)%MOD)
q[0] = pow(p[-1], MOD-2, MOD)
for i in range(1, N+1):
    q[i] = (N-i+1)*q[i-1]%MOD
q.reverse()

def nCk(n,k):
    if k > n or (k != 0 and n == 0):
        return 0
    elif k == 0:
        return 1
    else:
        return p[n]*q[k]%MOD*q[n-k]%MOD

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

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
N = 200000
p = [1] * (N+1)
q = [1] * (N+1)
for i in range(1, N+1):
    p[i] = (p[i-1]*(i)%MOD)
q[0] = pow(p[-1], MOD-2, MOD)
for i in range(1, N+1):
    q[i] = (N-i+1)*q[i-1]%MOD
q.reverse()

def nCk(n,k):
    if k > n or n == 0:
        return 0
    elif k == 0:
        return 1
    else:
        return p[n]*q[k]%MOD*q[n-k]%MOD

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

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

Submission status: Accepted

Solution code:
h,w,a,b = (int(i) for i in input().split())
mod,n,ans = 10**9+7,h+w-2,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(h-a): ans = (ans+comb(h+w-b-i-2,h-i-1)*comb(b+i-1,i))%mod
print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

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


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


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

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

Submission status: Accepted

Solution code:
import scipy.misc as scm

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

p = 10**9 + 7
ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(h+w)
rf = invfact(h+w, f)

for i in range(b, w):
    ans += (f[h-a+i-1] * rf[h-a-1] % p * rf[i] % p) * (f[a+w-i-2] * rf[a-1] % p * rf[w-i-1] % p) % p
    ans %= p 

print(ans)

Submission status: Accepted

Solution code:
import scipy.misc as scm

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

p = 10**9 + 7
ans = 0

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(h+w)
rf = invfact(h+w, f)

for i in range(w-b):
    wi = b + i
    ans += (f[h-a+wi-1] * rf[h-a-1] % p * rf[wi] % p) * (f[a+w-wi-2] * rf[a-1] % p * rf[w-wi-1] % p) % p
    ans %= p 

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
l = list(map(int,input().split()))
h,w,a,b = l[0],l[1],l[2],l[3]
def pow(x,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res*x % MOD
        x = x*x % MOD
        n = n >> 1
    return res

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

fact = [1]*1000000
inv = [1]*1000000

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

Submission status: Accepted

Solution code:
import itertools
import math
H,W,A,B=map(int,raw_input().split())

mod=10**9+7

FACT={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

#print FACT

def C(n,r):
	return (FACT[n]*pow(FACT[r],10**9+5 ,mod)*pow(FACT[n-r],10**9+5 ,mod)) %mod


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


print p

Submission status: Accepted

Solution code:
import itertools
import math
H,W,A,B=map(int,raw_input().split())

mod=10**9+7


FACT={}
FACT_INVERSE={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

#print FACT

def C(n,r):
	return (FACT[n]*pow(FACT[r],10**9+5 ,mod)*pow(FACT[n-r],10**9+5 ,mod)) %mod


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


print p

Submission status: Accepted

Solution code:
M = 10**9 + 7
L = 200000
 
Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M
 
def inverseFm(x):
    result = pow(Fm[x], M - 2, M)
    return result
 
def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result
 
def solve(H, W, A, B):
    result = 0
    for i in range(B + 1, W + 1):
        result += C(i + H - A - 1 - 1, i - 1) * C(W - i + A - 1, W - i)
    return result % M
 
H, W, A, B = [int(_) for _ in input().split()]
 
print(solve(H, W, A, B))

Submission status: Accepted

Solution code:
M = 10**9 + 7
L = 200000

Fm = {}
inverseFm = {}
x = 1
for i in range(L):
    Fm[i] = x
    x = x * (i + 1) % M

def inverseFm(x, cache={}):
    if x in cache:
        return cache[x]
    result = pow(Fm[x], M - 2, M)
    cache[x] = result
    return result

def C(n, r):
    result = Fm[n] * inverseFm(r) * inverseFm(n - r) % M
    return result

def solve(H, W, A, B):
    result = 0
    for i in range(B + 1, W + 1):
        result += C(i + H - A - 1 - 1, i - 1) * C(W - i + A - 1, W - i)
    return result % M

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

print(solve(H, W, A, B))

Submission status: Accepted

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

mod=10**9+7

#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod
#階乗計算
factorial=[1]
for i in range(1,H+W):
    factorial.append(factorial[i-1]*i %mod)
#逆元計算
inverse=[0]*(H+W)
inverse[H+W-1] = great_power(factorial[H+W-1], mod-2)
for i in range(H+W-2, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod
#combination計算
def nCr(n,r):
  return factorial[n] * inverse[r] * inverse[n-r] % mod

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

Submission status: Accepted

Solution code:
def d_Iroha_and_a_Grid(H, W, A, B):
    # フェルマーの小定理でnCrを定義
    n = H + W - 2
    M = 10**9 + 7
    factrial = [1] * (n + 2)
    for k in range(1, n + 2):
        factrial[k] = (factrial[k - 1] * k) % M

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

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

    ans = 0
    # 左上のマスの座標を(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で剰余を取る)
    for i in range(B, W):
        ans = (ans + nCr(H - A - 1 + i, H - A - 1, M) *
               nCr(A - 1 + W - 1 - i, A - 1, M)) % M
    return ans

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

Submission status: Accepted

Solution code:
mod = 1000000007

facto = [1]*200001
tmp = 1
for i in range(1,200001):
    tmp = (tmp*i)%mod
    facto[i] = tmp

def ncr(n,r):
    return (facto[n] * pow(facto[r],mod-2,mod) % mod) * pow(facto[n-r],mod-2,mod) % mod

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

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

Submission status: Accepted

Solution code:
def power_func(a,b,p):
  """a^b mod 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
 
H,W,A,B=map(int, input().split())
p=10**9+7
X=[1]  #階乗テーブル
for i in range(1,H+W-1):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(H+W-1)  #階乗の逆元テーブル
Y[H+W-2]=power_func(X[H+W-2],p-2,p)
for i in range(H+W-3,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

ans=0
for i in range(B,W):
  ans+=X[H-A-1+i]*X[A+W-2-i]*Y[H-A-1]*Y[i]*Y[A-1]*Y[W-1-i]
 
print(ans%p)

Submission status: Accepted

Solution code:
def power_func(a,b,p):
  """a^b mod 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

H,W,A,B=map(int, input().split())
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,H+W-1):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(H+W-1)  #階乗の逆元テーブル
Y[H+W-2]=power_func(X[H+W-2],p-2,p)
for i in range(H+W-3,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p
for i in range(B,W):
  ans+=(X[H-A-1+i]*X[A+W-2-i]*Y[H-A-1]*Y[i]*Y[A-1]*Y[W-1-i])%p

print(ans%p)

Submission status: Accepted

Solution code:
from math import factorial
H,W,A,B=map(int, input().split())
p=10**9+7
ans=0
X=[1,1]  #階乗テーブル
Y=[1,1]  #階乗の逆元テーブル
calc=[0,1]  #逆元計算用テーブル
for i in range( 2, H+W-2 ):
    X.append( ( X[-1] * i ) % p )
    calc.append( ( -calc[p % i] * (p//i) ) % p )
    Y.append( (Y[-1] * calc[-1]) % p )
for i in range(B,W):
  ans+=(X[H-A-1+i]*X[A+W-2-i]*Y[H-A-1]*Y[i]*Y[A-1]*Y[W-1-i])%p

print(ans%p)

Submission status: Accepted

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

"""042-d"""


import sys

def factorialMod(x, mod):
    """Calculate modulo of funcotial 'x'."""
    assert isinstance(x, int)
    assert x >= 0
    assert isinstance(mod, int)
    assert mod >= 0

    if x == 0:
        return 1
    return (x % mod) * factorialMod(x - 1, mod)

def binpow(p, e):
    """Bisection exponentiation."""
    assert isinstance(e, int)
    assert e >= 0

    a = 1
    while e:
        if e % 2 == 0:
            p = p * p
            e /= 2
        else:
            a = a * p
            e = e - 1
    return a


def main():
    """Main function."""
    mod = 1000000007
    H, W, A, B = map(int, sys.stdin.readline().split())

    fact_table = [1, 1]
    [fact_table.append((fact_table[-1] * i) % mod) for i in range(2, H + W - 1)]
    inv_fact_table = [pow(fact_table[i], 1000000005, 1000000007) for i in range(H + W - 1)]

    # print(inv_fact_table)

    def comb(n, r):
        """Calculate combination."""
        assert n >= r and n >= 0 and r >= 0

        return fact_table[n] * inv_fact_table[r] * inv_fact_table[n - r] % mod

    result = sum([comb(H - A + i - 1, H - A -1) * comb(W + A - i - 2, A - 1) for i in range(B, W)]) % mod

    print(result)

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

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

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

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

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

ANS=0

for i in range(N):
    ANS=(ANS+com(H-A-1+B,B+i, mod)*com(W+A-1-B,A+i, mod))%mod
print(ANS)

Submission status: Accepted

Solution code:



class Combination:
    def __init__(self, mod):
        self.mod = mod
        self.fact = [1] * (2 * 10 ** 5 + 1)
        for i in range(1, 2 * 10 ** 5 + 1):
            self.fact[i] = i * self.fact[i - 1] % self.mod

    def nCr(self, n, k):
        a = self.fact[n] % self.mod
        b = (self.fact[k] * self.fact[n - k]) % self.mod
        c = pow(b, self.mod - 2, self.mod)
        return a * c % self.mod


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

    ans = 0
    for i in range(W - B):
        h, w = H - A - 1, B + i
        a = c.nCr(h + w, h) % MOD

        h, w = A - 1, W - B - i - 1
        b = c.nCr(h + w, h) % MOD

        ans = (ans + a * b) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

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

ans = 0
for i in range(B, W):
    # (h-a+i)Ci * (a+W-i)Ca 
    ans += comb(H-A+i-1, i) * comb(A+W-i-2, A-1) % mod
    
print(ans%mod)

Submission status: Accepted

Solution code:
import operator as op
from functools import reduce
from math import factorial
import sys

modulus = 1000000007

factorial = [1, 1]
for i in range(2, 2000001):
    factorial.append(factorial[-1] * i % modulus)

factorial_inv_rev = [pow(factorial[-1], 1000000005, modulus)]
for i in range(len(factorial)-1, 1, -1):
    factorial_inv_rev.append(factorial_inv_rev[-1] * i % modulus)

def ncr(n, r):
    if n==r or r==0:
        return 1
    else:
        numelator = factorial[n]
        denominator = factorial_inv_rev[-r] * factorial_inv_rev[r-n]
        return numelator * denominator % modulus

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

points = [(i, j) for i, j in zip(range(h-a-1, -1, -1), range(b, w))]

former = [ncr(i+j, i) for i, j in points]
latter = [ncr(h-i-1+w-j-1, h-i-1) for i, j in points]

print(sum(f*l for f, l in zip(former, latter)) % modulus)

Submission status: Accepted

Solution code:
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def mul(a,b):
  return (a*b) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

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

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

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[n-1], n)
  factorical.append(f)
  if(n <= max(H,W)):
    factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
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)

    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)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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

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

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

print(ans % mod)

Submission status: Accepted

Solution code:
C = int(1e9) + 7
H, W, A, B = map(int, input().split())

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

factinv = [1] * (H + W -2)
factinv[H + W - 3] = pow(fact[H + W -3], C-2, C)

for x in reversed(range(2, H + W -3)):
	factinv[x] = ( factinv[x+1] * (x+1) ) % C

def nCr(n,r):
	return ( fact[n] * factinv[r] * factinv[n-r] ) % C

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