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: Time Limit Exceeded

Solution code:
C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

# 1000000005 = 2^29 + 2^28 + 2^27 + 2^25 + 2^24 + 2^23 + 2^20 + 2^19 + 2^17 + 2^15 + 2^14 + 2^11 + 2^9 + 2^2 + 1

def pow(n):
    ans = n
    for i in range(1, 30):
        n = (n * n) % C
        if i in {29, 28, 27, 25, 24, 23, 20, 19, 17, 15, 14, 11, 9, 2}:
            ans = (ans * n) % C
    return ans

fact = [1]
factinv = [1] # dummy
for x in range(1, h + w - 2):
    fact.append((x * fact[x - 1]) % C)
    # factinv.append(pow(x)) # <- this won't work, why?
    factinv.append((pow(x) * factinv[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)

Submission status: Time Limit Exceeded

Solution code:
H,W,A,B = [int(n) for n in input().split(" ")]
answers = []
for total in range(B,W):
    disp = 1
    for n in range(1,total+(H-A)):
        disp *= n
    for m in range(1,H-A ):
        disp //= m
    for t in range(1,total + 1):
        disp //= t
    answers.append(disp)
for cnt,total in enumerate(range(B,W)):
    disp = 1
    for n in range(1,(W - total - 1) + (H - (H - A))):
        disp  *= n
    for m in range(1,H- (H - A)):
        disp //= m
    for t in range(1,W-total):
        disp //= t
    answers[cnt] *= disp
print(sum(answers) %( 10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def read():
    return map(int, input().split())


h, w, a, b = read()
m = 10 ** 9 + 7

line1 = [1 for _ in range(w)]
line2 = [0 for _ in range(w)]
for _ in range(1, h - a):
    line2[0] = 1
    for j in range(1, w):
        line2[j] = (line2[j - 1] + line1[j]) % m
    line1 = line2
    line2 = [0 for _ in range(w)]

line1 = line1[b:]
line2 = [0 for _ in range(w - b)]

for _ in range(a):
    line2[0] = line1[0]
    for j in range(1, w - b):
        line2[j] = (line2[j - 1] + line1[j]) % m
    line1 = line2
    line2 = [0 for _ in range(w - b)]

print(line1[-1])

Submission status: Memory Limit Exceeded

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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()
     

fac = [-1] * (10**7+1)
inv = [-1] * (10**7+1)
finv = [-1] * (10**7+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

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

initNCMMod(10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()

Submission status: Accepted

Solution code:
MODD = 10**9 + 7 

def modinv(a,m)-> int:
    b = m
    u = 1
    v = 0
    while (b):
        t = a // b
        a -= t * b
        a,b= b,a
        u -= t * v
        u,v= v,u
    u %= m
    if (u < 0):
        u += m
    return u


fac=[1]*200001
infac=[1]*200001
aaa=1
for i in range(1,200001):
    aaa=(aaa*i)%MODD
    fac[i]=aaa
    infac[i]=modinv(aaa,MODD)
    #print(fac[i])

import math as m

def perm(x,y,z) -> int:
    #print(fac[x]//(fac[y]*fac[z]))   
    return ((fac[x]*infac[y]*infac[z])%MODD)

h,w,a,b= [int(x) for x in input().split()]
A = h-a
B = b-1
C = h-1
D = w-b-1
j=0
k=B
kl = C
jl = D
ans = 0
for i in range(A):
  ans+=perm(B+i,B,i)*perm(C+D-i,C-i,D)
print(ans%MODD)

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
#コンビネーション逆元
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


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


for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
ans=cmb(h+w-2,h-1,mod)
for i in range(h-a+1,h+1):
    ans-=cmb(i+b-2,i-1,mod)*cmb(h-i+w-b-1,w-b-1,mod)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7

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

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


def perm(n, r):
    return factorial(n) // factorial(r)


def gcb(a, b):
    if b == 0:
        return a
    else:
        return gcb(b, a % b)


def lcm(a, b):
    d = gcb(a, b)
    return int(a / d * b)


def surP(x):
    return x % MOD


def main():
    # ------ 入力 ------#
    h, w, a, b = list(map(int, input().split()))     # スペース区切り連続数字

    # ------ 処理 ------#
    f = combInit(h + w)
    res = 0
    for i in range(b, w):
        res += comb((h-1-a)+i, i, f) * comb((a-1)+(w-1-i), w-1-i, f)

    out = surP(res)
    # ------ 出力 ------#
    print("{}".format(out))
    # if flg == 0:
    #     print("YES")
    # else:
    #     print("NO")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

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

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

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

Submission status: Accepted

Solution code:
P = 10**9+7
fac = [1]
ifac = [1]
ff = 1
for i in range(1,200001):
  ff *= i
  ff %= P
  fac.append(ff)
  ifac.append(pow(ff, P-2, P))
def ncr(n, r): 
  return (fac[n] * ifac[r] % P * ifac[n-r] % P);

h,w,a,b = map(int,input().split())
s = 0
nC = b-1
kC = 0
nD = w-b-1+h-1
kD = h-1
for i in range(h-a):
  C = ncr(nC, kC)
  D = ncr(nD, kD)
  s = (s + C * D) % P
  nC += 1
  kC += 1
  kD -= 1
  nD -= 1
print(s)

Submission status: Accepted

Solution code:
from math import comb
h,w,a,b = map(int,input().split())
s = 0
nC = b-1
kC = 0
nD = w-b-1+h-1
kD = h-1
p = 1000000007
fac = [1]
ff = 1
for i in range(1,200001):
  ff *= i
  ff %= p
  fac.append(ff)
def ncr(n, r, p): 
  return (fac[n] * pow(fac[r], p-2, p) % p * pow(fac[n-r], p-2, p) % p);

for i in range(h-a):
  C = ncr(nC, kC, 1000000007)
  D = ncr(nD, kD, 1000000007)
  s = (s + C * D) % 1000000007
  nC += 1
  kC += 1
  kD -= 1
  nD -= 1
print(s)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

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

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

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

comb = Combination(10**6)

def main():
    H, W, A, B = map(int, input().split())
    ans = 0
    for i in range(1, H - A + 1):
        ans += comb(i + B - 2, i - 1) * comb(H - i + W - B - 1, H - i)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

MAX = 510000
MOD = 10**9 + 7

def MakeTable():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

def COM(n, k):
    if n < k:
        return 0
    elif n < 0 or k < 0:
        return 0
    else:
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

H, W, A, B = map(int, input().split())
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

N = min(H-A, W-B)
x, y = 0, 0
result = 0

MakeTable()

for _ in range(N):
    n1 = H-A-1+B+x-y
    n2 = A+W-1-B-x+y
    result += (COM(n1, B+x) * COM(n2, A+y)) % MOD
    x += 1
    y += 1

print(result%MOD)

Submission status: Accepted

Solution code:
#縦H A

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

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

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H,W,A,B=map(int,input().split())
ans=0
for i in range(H-A):
  ans+=cmb(B+i-1,B-1,mod) * cmb(H-i+W-B-2,W-B-1,mod)
print(ans%mod)
# 1 1 1
# $ 1 2

Submission status: Accepted

Solution code:
def permutation(n, k, mod):
    s = 1
    for _ in range(k):
        s *= n
        s %= mod
        n -= 1
    return s

def factorial(n, mod):
    s = 1
    for i in range(1, n + 1):
        s *= i
        s %= mod
    return s

h, w, a, b = map(int, input().split())
mod = pow(10, 9) + 7
x = h - a + b - 1
y = w - b + a - 2
p = permutation(x, h - a - 1, mod) * permutation(y, a - 1, mod) % mod
ans = p
for _ in range(w - b - 1):
    x += 1
    p = p * x * (y - (a - 1)) * pow((x - (h - a - 1)) * y, mod - 2, mod) % mod
    y -= 1
    ans += p
    ans %= mod
ans = ans * pow(factorial(a - 1, mod), mod - 2, mod) * pow(factorial(h - a - 1, mod), mod - 2, mod) % mod
print(ans)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, open(0).read().split())
MOD = 10**9+7
 
factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)
 
for i in range(H + W):
    factorials[i+1] = factorials[i] * (i + 1) % MOD

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

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
# total = modcomb(H + W - 2, W - 1, MOD)
total = 0
 
# for i in range(B):
for i in range(B, W):
    total += modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD

print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

tmp = 1
for i in range(H + W):
    tmp = tmp * (i + 1) % MOD
    factorials[i+1] = tmp

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
# total = modcomb(H + W - 2, W - 1, MOD)
total = 0
 
# for i in range(B):
for i in range(B, W):
    total += modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

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

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
# total = modcomb(H + W - 2, W - 1, MOD)
total = 0
 
# for i in range(B):
for i in range(B, W):
    total += modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

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

inv_factorials = list(map(lambda n: pow(n, -1, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

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

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD) % MOD
    total %= MOD
 
print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

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

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] % MOD * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD)
    total %= MOD
 
print(total)

Submission status: Accepted

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

factorials = [1] * (H + W + 1)
inv_factorials = [1] * (H + W + 1)

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

inv_factorials = list(map(lambda n: pow(n, MOD - 2, MOD), factorials))

def modcomb(m, n, mod):
    return factorials[m] * inv_factorials[n] * inv_factorials[m - n] % MOD
 
total = modcomb(H + W - 2, W - 1, MOD)
 
for i in range(B):
    total -= modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD)
    total %= MOD
 
print(total)

Submission status: Accepted

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

def modperm(m, n, mod):
    p = 1
    for i in range(n):
        p = p * (m - i) % mod
    return p

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = modperm(m, n, mod)
    q = pow(modperm(n, n, mod), mod - 2, mod)
    return p * q % mod

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i
#     print(a,b,c,d)
    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, MOD - 2, MOD) % MOD
    tmp = tmp * pow(d, MOD - 2, MOD) % MOD
#     print(tmp)
    total = (total - tmp) % MOD

print(total)

Submission status: Accepted

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

def modcomb(m, n, mod):
    if n > m - n:
        n = m - n
    p = 1
    q = 1
    for i in range(n):
        p = p * (m - i) % mod
        q = q * (i + 1) % mod
    result = p * pow(q, mod - 2, mod) % mod
    return result

total = modcomb(H + W - 2, W - 1, MOD)

tmp = modcomb(A + W - 2, W - 1, MOD)
total -= tmp

for i in range(B - 1):
    a = H - A + i
    b = i + 1
    c = W - i - 1
    d = W + A - 2 - i
#     print(a,b,c,d)
    tmp = tmp * a * c % MOD
    tmp = tmp * pow(b, -1, MOD) % MOD
    tmp = tmp * pow(d, -1, MOD) % MOD
#     print(tmp)
    total = (total - tmp) % MOD

print(total)

Submission status: Accepted

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

for I in range(H-1):
  ans = 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
  ans+=C

print(ans%M)

Submission status: Accepted

Solution code:
class Factorials:
    # nに十分大きい数を入力
    def __init__(self, n, mod):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

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

f = Factorials(2 * (10 ** 5), mod)
if h - a < w - b:
    num = h - a
else:
    num = w - b

ans = 0
for i in range(num):
    x = h - a - i
    y = b + i + 1

    ans += f.comb(x + y - 2, x - 1) * f.comb(h + w - x - y, h - x)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
class mod_comb_k():
  def __init__(self, MAX_N = 10**6, mod = 10**9+7):
    self.fact = [1]
    self.fact_inv = [0] * (MAX_N + 4)
    self.mod = mod
    if MAX_N > mod:print('MAX_N > mod !')
    for i in range(MAX_N + 3):
      self.fact.append(self.fact[-1] * (i + 1) % self.mod)
    self.fact_inv[-1] = pow(self.fact[-1], self.mod - 2, self.mod)
    for i in range(MAX_N + 2, -1, -1):
      self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod
  def comb(self, n, k):
    if n < k:
      print('n < k !')
      return 0
    else:return self.fact[n] * self.fact_inv[k] % self.mod * self.fact_inv[n - k] % self.mod
h,w,a,b=map(int,input().split())
c=mod_comb_k()
mod=10**9+7
ans=c.comb(h+w-2,w-1)
for i in range(b):
  ans-=(c.comb(i+h-a-1,i)*c.comb(a+w-2-i,a-1))%mod
print(ans%mod)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
N = h + w + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
a += 1
b += 1
n = h - a + b - 1
n2 = w - b + a - 1
while a <= h and b <= w:
    ans += nCk(n, b - 1) * nCk(n2, w - b)
    ans %= MOD
    a += 1
    b += 1
print(ans)

Submission status: Accepted

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

n = 2 * 10 ** 5
k = 2 * 10 ** 5
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def prepare_binomial_coefficients(n, k):
    for i in range(1,n+1):
        bc_num[i] = i * bc_num[i-1] % mod
    bc_num[0] = 0
    for i in range(1,k+1):
        bc_den[i] = modinv_table[i] * bc_den[i-1] % mod
    return

def binomial_coefficients(n, k):
    if n == 0 and k == 0:
        return 1
    return bc_num[n] * bc_den[k] * bc_den[n-k] % mod

bc_num = [1]*(n+1)
bc_den = [1]*(n+1)
prepare_binomial_coefficients(n, n)

mids = [0]*(w-b)
dis_mid = h - a - 1
for i in range(w-b):
    mids[i] = binomial_coefficients(dis_mid+i+b,i+b)

#print(mids)

mids_down = [0]*(w-b)
dis_mid = a
for i in range(w-b):
    mids_down[i] = binomial_coefficients(dis_mid+w-b-i-1,w-b-i-1)

#print(mids_down)

for i in range(w-b-1):
    mids_down[i] -= mids_down[i+1]

#print(mids_down)

for i in range(w-b):
    mids[i] = (mids[i] * mids_down[i]) % mod

#print(mids)

print(sum(mids)%mod)

Submission status: Accepted

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

n = 2 * 10 ** 5
k = 2 * 10 ** 5
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def prepare_binomial_coefficients(n, k):
    for i in range(1,n+1):
        bc_num[i] = i * bc_num[i-1] % mod
    bc_num[0] = 0
    for i in range(1,k+1):
        bc_den[i] = modinv_table[i] * bc_den[i-1] % mod
    return

def binomial_coefficients(n, k):
    if n == 0 and k == 0:
        return 1
    return bc_num[n] * bc_den[k] * bc_den[n-k] % mod

bc_num = [1]*(n+1)
bc_den = [1]*(n+1)
prepare_binomial_coefficients(n, n)

mids = [0]*(w-b)
dis_mid = h - a - 1
for i in range(w-b):
    mids[i] = binomial_coefficients(dis_mid+i+b,i+b)

#print(mids)

mids_down = [0]*(w-b)
dis_mid = a
for i in range(w-b):
    mids_down[i] = binomial_coefficients(dis_mid+w-b-i-1,w-b-i-1)

#print(mids_down)

for i in range(w-b-1):
    mids_down[i] -= mids_down[i+1]

#print(mids_down)

for i in range(w-b):
    mids[i] = (mids[i] * mids_down[i]) % mod

#print(mids)

print(sum(mids)%mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
h, w, a, b = map(int, input().split())
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (h + w + 1)
fi = [1] * (h + w + 1)
for i in range(1, h + w + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
ans = 0
for i in range(h - a):
    ans += comb(b + i - 1, b - 1) * comb(h + w - b - i - 2, w - b - 1)
    ans %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)
 
def mul(x, y, mod):
  x %= mod
  y %= mod
  return x * y % mod
 
def div(x, y, mod):
  x %= mod
  y %= mod
  return x * mod_pow(y, mod - 2, mod) % mod
 
@lru_cache(maxsize=None)
def mod_pow(a, p, mod):
  if p == 0:
    return 1
  if p % 2 == 0:
    root = mod_pow(a, p / 2, mod)
    return root * root % mod
  else:
    return a * mod_pow(a, p - 1, mod) % mod
 
def dnm(n, mod, factorials):
  denominators = [0] * (n + 1)
  denominators[n] = div(1, factorials, mod)
  for i in reversed(range(n)):
    denominators[i] = mul(denominators[i+1], i+1, mod)
  return denominators
 
def nmr(n, mod):
  factorials = [0] * (n + 1)
  factorials[0] = 1
  for i in range(n):
    factorials[i + 1] = (i + 1) * factorials[i] % mod
  return factorials
 
def cmb(a, b, mod, factorials, factorial_divs):
    if len(factorials) == 0:
        raise
    af = factorials[a]
    bf = factorial_divs[b]
    abf = factorial_divs[a - b]
    return mul(mul(af, bf, mod), abf, mod)
 
MOD=10**9+7
H,W,A,B=map(int,input().split())
ans = 0
 
n = nmr(H+W-2, MOD)
d = dnm(H+W-2, MOD, n[H+W-2])
 
for i in range(H-A):
  x = cmb(B-1+i, B-1, MOD, n, d)
  y = cmb(H+W-3-(B-1+i), W-B-1, MOD, n, d)
  ans += x * y % MOD
  ans %= MOD
 
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class CmbMod:
    def __init__(self, n, p):
        """
        二項係数nCr(n個の区別できるものからr個のものを選ぶ組み合わせの数)をpで割った余りを求める
        """
        self.n = n
        self.p = p
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

    def cmb_mod(self, n, r):
        """
        二項係数nCr(mod p)をO(r)にて計算。nが大きいがrは小さい時に使用。
        """
        numer, denom = 1, 1
        for i in range(r):
            numer = (numer * (n - i)) % self.p
            denom = (denom * (i + 1)) % self.p
        return (numer * pow(denom, self.p - 2, self.p)) % self.p

    def prep(self):
        """
        二項係数nCr(mod p)をO(1)で求める為の前処理をO(N)にて実行。
        """
        for i in range(2, self.n + 1):
            self.fact.append((self.fact[-1] * i) % self.p)
            self.inv.append((-self.inv[self.p % i] * (self.p // i)) % self.p)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % self.p)

    def cmb_mod_with_prep(self, n, r):
        """
        二項係数nCr(mod p)をO(1)で求める。事前にprepを実行する事。
        """
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.p


def resolve():
    H, W, A, B = map(int, input().split())
    H -= 1
    W -= 1
    cmb = CmbMod(H + W, mod)
    cmb.prep()
    total = cmb.cmb_mod_with_prep(H + W, H)
    for w in range(B):
        tmp = (cmb.cmb_mod_with_prep(H - A + w, w) * cmb.cmb_mod_with_prep(A - 1 + W - w, A - 1)) % mod
        total -= tmp
        total %= mod
    print(total)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
LIMIT = 2 * 10 ** 5
fac = [0] * (LIMIT + 10)
fac[0] = 1
inv = [0] * (LIMIT + 10)
MOD = 1_000_000_007
n = 1
for i in range(1, LIMIT + 1):
    n *= i
    n %= MOD
    fac[i] = n
inv[LIMIT] = pow(fac[LIMIT], MOD - 2, MOD)
for i in range(LIMIT, -1, -1):
    inv[i - 1] = (inv[i] * i) % MOD
def C(n, r):
    return (fac[n] * inv[n-r] * inv[r]) % MOD

H, W, A, B = map(int, input().split())
ans = 0
B1 = B - 1
WB1 = W - B - 1
for i in range(H - A):
    ans += C(i + B1, B1) * C(H - i - 1 + WB1, WB1)
    ans %= MOD
print(ans)

Submission status: Accepted

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

# H行W列 左下から縦A横B

def mod(num):
    return num % (10 ** 9 + 7)
    
n = H + W + 1

fac = [0] * n
rev = [0] * n

fac[0] = 1

for i in range(1, n):
    fac[i] = mod(fac[i-1] * i)


# 逆元の計算 x**(-1) ≡ x**(10**9 + 5) (mod 10**9 + 7)
rev[n-1] = pow(fac[n-1], 10**9 + 5, 10**9 + 7)

for i in range(n - 2, 0, -1):
    rev[i] = mod(rev[i + 1] * (i + 1))

rev[0] = 1

t1 = [0] * (W - B)

for i in range(W - B):
    t1[i] = mod(fac[H - A - 1 + i + B] * mod(rev[B + i] * rev[H - A - 1]))
    
res = 0

for i in range(W - B):
    r = t1[i] * mod(fac[A - 1 + W - B - 1 - i] * mod(rev[A - 1] * rev[W - B - 1 - i]))
    res = mod(res + r)
    
print(res)