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: Wrong Answer

Solution code:
MODD = 10**9 + 7 

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

import math as m

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

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(B,B+A):
  ans+=perm(i,k,i-k)*perm(kl+jl-(i-k),kl-(i-k),jl)
print(ans%MODD)

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int,input().split())
G = [[0]*W for _ in range(H)]
MOD = 10**9+7
for i in range(W):
  G[0][i] = 1
for i in range(H):
  G[i][0] = 1
for i in range(H-A, H):
  for j in range(B):
    G[i][j] = -float('inf')
  
for i in range(1, H):
  for j in range(1, W):
    a = max(G[i-1][j], 0)
    b = max(G[i][j-1], 0)
    G[i][j]+=a+b
    G[i][j]%=MOD
print(G[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int,input().split())
G = [[0]*W for _ in range(H)]
for i in range(W):
  G[0][i] = 1
for i in range(H):
  G[i][0] = 1
for i in range(H-A, H):
  for j in range(B):
    G[i][j] = -float('inf')
  
for i in range(1, H):
  for j in range(1, W):
    a = max(G[i-1][j], 0)
    b = max(G[i][j-1], 0)
    G[i][j]+=a+b
print(G[H-1][W-1])

Submission status: Wrong Answer

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

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

ans = 0
for i in range(B,W):
    ans += Fact[H-A-1+i]/Fact[H-A-1]/Fact[i] * Fact[A-1+W-1-i]/Fact[A-1]/Fact[W-1-i]
    ans %= mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())
from math import factorial
mod = 1000000007
Fact = [factorial(x)%mod for x in range(H+W)]

ans = 0
for i in range(B,W):
    ans += Fact[H-A-1+i]/Fact[H-A-1]/Fact[i] * Fact[A-1+W-1-i]/Fact[A-1]/Fact[W-1-i]
print(int(ans%mod))

Submission status: Wrong Answer

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 = total - modcomb(H - A - 1 + i, i, MOD) * modcomb(A - 1 + W - 1 - i, W - 1 - i, MOD)
 
print(total)

Submission status: Wrong Answer

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

from scipy.special import comb

def main():
   

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

    whole = 0
    part = 0

    H = H - 1
    W = W - 1
    A = A - 1
    B = B - 1

    whole = comb((H + W), H, exact=True)

    part = comb((A + B), A, exact=True)

    ans = whole - part

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D - いろはちゃんとマス目

from scipy.special import comb

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

whole = 0
part = 0

whole = comb((H + W) - 2, H - 1, exact=True)

part = comb((A + B), A, exact=True)

ans = whole - part

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,a,b=map(int,input().split())
fac=[0]*200001#iの階乗mod(1000000007)
inv=[0]*200001#iの逆元mod(1000000007)
fac[0]=1
ans=0
for i in range(1,200001):
    fac[i]=fac[i-1]*i%1000000007
inv[200000]=pow(fac[200000],1000000005,1000000007)
for i in range(199999,0,-1):
    inv[i]=(inv[i+1]*(i+1))%1000000007
for i in range(h-a):
    if i==0:
        if h==1:
            x=1
        else:
            x=(fac[w-b+h-2
                   -i]*inv[w-1-b]*inv[h-1-i])%1000000007
    else:
        x=((fac[b-1+i]*inv[b-1]*inv[i])%1000000007)*((fac[w-b+h-2-i]*inv[w-b-1]*inv[h-1-i])%1000000007)
    ans=(ans+x)%1000000007
print(ans)

Submission status: Wrong Answer

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

p=10**9+7
#p=127

def modp_factorial(n):
    s=1
    for x in range(1,h+1):
        s=(s*x) % p
    return s
def modp_prod(lst):
    s=1
    for x in lst:
        s=(s*x)%p
    return s
def inv(n):
    s=1
    q=p-2
    while q>0:
        if q&1:
            s=s*n % p
        n=n*n % p
        q>>=1
    return s

l=[1]
f=1
for x in range(1,h+w+1):
    f=f*x % p
    l.append(f)
invl=[inv(l[-1])]
for n in range(h+w,1,-1):
    invl.append((invl[-1]*n) % p)
invl.append(1)
invl.reverse()


s=0
for x in range(1,h-a+1):
    s=s+modp_prod([l[x+b-2],invl[x-1],invl[b-1]\
        ,l[w-b+h-x-1],invl[h-x],invl[w-b-1]])% p
print(s)

Submission status: Wrong Answer

Solution code:
from scipy.special import comb
H, W, A, B = map(int, input().split())
ans = 0

for i in range(W - B+1):
    ans += comb(H - A + B + i, H-A, exact=True) * \
        comb(W - B + A - i, A, exact=True)

ans = int(ans % (10**9+7))

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

H,W,A,B = map(int,input().split())
rt = 0
for i in range(H-A):
  rt += (factorial(i+B-1) * factorial(H-i+W-B-2)) // (factorial(i) * factorial(B-1) * factorial(H-i-1) * factorial(W-B-1))
print(rt % 100000007)

Submission status: Wrong Answer

Solution code:
from math import factorial

H,W,A,B = map(int,input().split())
rt = 1
for i in range(H-A-1):
  rt += (factorial(i+B) * factorial(H-i+W-B)) // (factorial(i+1) * factorial(B) * factorial(H-i) * factorial(W-B))
  print(rt)
print(rt % 100000007)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
    n = LI()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def frac(n):
  m=1
  for i in range(1, n+1):
    m = m * i % 1000000007
  return m % 1000000007

(h,w,a,b)=[int(x) for x in input().split()]
ans=0
for i in range(1,w-b+1):
  ans+=(((frac(h-a-1+w-i)/(frac(h-a-1)*frac(w-i)))%1000000007)*((frac(a-1+i-1)/(frac(a-1)*frac(i-1)))%1000000007))%1000000007
print(int(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import factorial 
h,w,a,b=map(int,input().split())
res=0
fact=[]
for i in range(h+w):
  fact.append(factorial(i))
for i in range(b+1,w+1):
	first=fact[i+h-a-2]//(fact[i-1]*fact[h-a-1])
	second=fact[w-i+a-1]//(fact[w-i]*fact[a-1])
	res+=first*second
print(res)

Submission status: Wrong Answer

Solution code:
def conbi(n, r):
    bunbo = 1
    bunshi = 1
    if n / 2 < r:
        r = n - r
    while r > 0:
        bunbo *= r
        bunshi *= n
        r -= 1
        n -= 1
    return bunshi // bunbo

def conbi_mod(n, r):
    return conbi(n, r) % (10 ** 9 + 7)
    


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

if B < W / 2:
    not_ans = 0
    total = conbi_mod((H - 1) + (W - 1), H-1)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi_mod((sq1h -1) + (sq1w - 1), (sq1h -1)) * conbi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1))
        not_ans += n
    ans = total - not_ans
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1)) * conbi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1))
        ans += n
    print(ans)

Submission status: Wrong Answer

Solution code:
def conbi(n, r):
    bunbo = 1
    bunshi = 1
    if n / 2 < r:
        r = n - r
    while r > 0:
        bunbo *= r
        bunshi *= n
        r -= 1
        n -= 1
    return bunshi // bunbo

def conbi_mod(n, r):
    return conbi(n, r) % (10 ** 9 + 7)
    


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

if B < W / 2:
    not_ans = 0
    total = conbi_mod((H - 1) + (W - 1), H-1)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h -1) + (sq1w - 1), (sq1h -1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        not_ans += n
    ans = total - not_ans
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h - 1) + (sq1w - 1), (sq1h - 1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        ans += n
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def pow(x, n, p):
	tmp = 1
	while n:
		if n%2:
			tmp = tmp*x%mod
		x = x*x%mod
		n >>= 1
	return tmp%mod

print(pow(2, 10, mod))


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

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

print(ans)

Submission status: Wrong Answer

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

def comb(n,r):
    res = 1
    fac = 1
    for i in range(r):
        res *= n-i
        res %= MOD
        fac *= i+1
        fac %= MOD
    return res*pow(fac,MOD-2,MOD)%MOD   

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

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    ans += comb(h-a-1 + j, j, exact=True) * comb(a+w-2 - j, w-1 - j, exact=True)
ans %= 100000007
print(ans)

Submission status: Wrong Answer

Solution code:
import math


def conbination(m, n):
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))


h, w, a, b = (int(x) for x in input().split())
ans = 0
for j in range(b, w):
    ans += conbination(h - a + j - 1, j) * conbination(a + w - j - 2, w - j - 1)
ans %= 100000007
print(ans)

Submission status: Wrong Answer

Solution code:

a,b,c,d = list(map(int, input().split()))

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10**9+7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
    
def wh(w,h):
    return cmb(w+h,w,10**9+7)

ans = wh(b-1,a-1)
print(ans)

for i in range(d):
    tmp = wh(i,a-c-1) * wh(c-1,b-i-1) % p
    ans += p
    ans -= tmp
    ans %= p
    #print(ans)
    
print(ans)

Submission status: Wrong Answer

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

total = 0
tmp1, tmp2 = 1, 1		# 初期化
tmp3, tmp4 = 1, 1		# 初期化
for i in range(B,W,1):
  conv1, conv2 = 0, 0	# 初期化
  if i == B:
    for j in range(i):
      tmp1 *= i+(H-A-1)-j
    tmp1 %= (10**9+7)
    for j in range(i, 0, -1):
      tmp2 *= j
    tmp2 %= (10**9+7)
  else:
    tmp1 *= i+(H-A-1)
    tmp1 %= (10**9+7)
    tmp2 *= i
    tmp2 %= (10**9+7)
  conv1 = tmp1/tmp2
  
  if i == B:
    for j in range(W-1-i):
      tmp3 *= (A-1)+(W-1-i)-j
    tmp3 %= (10**9+7)
    for j in range(W-1-i, 0, -1):
      tmp4 *= j
    tmp4 %= (10**9+7)
  else:
    tmp3 *= W-1-i+1
    tmp3 %= (10**9+7)
    tmp4 *= (A-1)+(W-1-i)+1
    tmp4 %= (10**9+7)
  conv2 = tmp3/tmp4
  total += conv1*conv2
print(int(total))

Submission status: Wrong Answer

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

# 全組み合わせ数
total = 1
min_num = min(H-1, W-1)
for i in range(min_num):
  total *= (H+W-2)-i
total %= (10**9+7)
tmp = 1
for i in range(min_num, 0, -1):
  tmp *= i
tmp %= (10**9+7)
total /= tmp
#print(int(total))

# 除外する組み合わせ数
remove_num = 0
if A == 1:
  remove_num = 1
else:
  if B == 1:
    remove_num = A
  else:
    for i in range(A):
      remove_num1 = 1   # 初期化
      remove_num2 = 1   # 初期化
      if i == 0:
        for j in range(H-1):
          remove_num1 *= (H-1)+(B-1)-j
        remove_num1 %= (10**9+7)
        tmp = 1
        for j in range(H-1, 0, -1):
          tmp *= j
        tmp %= (10**9+7)
        remove_num1 /= tmp
        remove_num += remove_num1
      else:
        for j in range(H-1-i):
          remove_num1 *= (H-1-i)+(B-1)-j
        remove_num1 %= (10**9+7)
        tmp = 1
        for j in range(H-1-i, 0, -1):
          tmp *= j
        tmp %= (10**9+7)
        remove_num1 /= tmp
        for j in range(i):
          remove_num2 *= i + W-B-1-j
        remove_num2 %= (10**9+7)
        tmp = 1
        for j in range(i, 0, -1):
          tmp *= j
        tmp %= (10**9+7)
        remove_num2 /= tmp
        remove_num += remove_num1*remove_num2
print(int(total-remove_num))

Submission status: Wrong Answer

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 )
 
all_comb = cmb(h+w-2, h-1, mod)
 
for i in range(a):
    all_comb=all_comb-(cmb(h+b-i-2, h-i-1, mod)*cmb(w-b-1+i, i, mod))
 
print(int(all_comb))

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
fac_table = [1 for i in range(200001)]
inv_table = [1 for i in range(200001)]


def make_table(h, w):

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


def comb(n, r):
    return fac_table[n] * inv_table[n - r] % mod * inv_table[r] % mod


def resolve():
    H, W, A, B = map(int, input().split())
    make_table(H, W)
    print(
        sum(
            [
                comb(H - A - 1 + i, i) * comb(A - 1 + W - i - 1, A - 1) % mod
                for i in range(B, W)
            ]
        )
        % mod
    )

Submission status: Wrong Answer

Solution code:
h, w, a, b = map(int, input().split())
f = [[0 for i in range(w)] for j in range(h)]
for i in range(w):
  f[0][i] = 1
for i in range(h-a):
  f[i][0] = 1
for i in range(1, h):
  for j in range(1, w):
    if not (i >= h-a and j <= b-1):
      f[i][j] = f[i-1][j] + f[i][j-1]
print(f[h-1][w-1])

Submission status: Wrong Answer

Solution code:
def main():
    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)

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

    ans = cmb((H+W-2), min(H, W)-1, mod)

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


main()

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

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

dp = [[0 for i in range(h+1)] for j in range(w+1)]

for i in range(w):
    for j in range(h):
        dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]
        if i == 0 and j == 0:
            dp[i+1][j+1] = 1
        if i < b and j >= h-a:
            dp[i+1][j+1] = 0
print(dp[w][h])

Submission status: Wrong Answer

Solution code:
from sys import stdin
from operator import itemgetter
import math
# stdin = open("sample.txt")

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

path_list = list(range(W-B))
path_list2 = list(range(0))
path_list.reverse()
for path in path_list:
    path_list2.append(math.factorial((W-path-1)+(H-A-1))//math.factorial(W-path-1)//math.factorial(H-A-1))
 
H2 = A+1
W2 = W-B
path2_list = [[0] * (W2) for i in range(H2)]

h = 0
w = 0
while h < H2:
    path2_list[h][0] = path_list2[0]
    h += 1
while w < W2:
    path2_list[0][w] = path_list2[w]
    w += 1

h2 = 1
w2 = 1
ans = 0
while h2 <= H2-1 and w2 <= W2-1:
    ans = (path2_list[h2-1][w2] + path2_list[h2][w2-1])
    path2_list[h2][w2] = ans
    if w2 == W2-1:
        h2 += 1
        w2 = 1
    else:
        w2 += 1
print(path2_list[H2-1][W2-1])

Submission status: Wrong Answer

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

Submission status: Wrong Answer

Solution code:
def f(x):
    if x==0:
        return 1
    else:
        fac=1
        for i in range(1,x+1):
            fac*=i
        return fac
def c(x,y):
    return f(x+y)//(f(x)*f(y))
h,w,a,b=map(int,input().split())
ans=0
ans+=c((h-a-1),(b))*c((a),(w-b-1))
for i in range(h-a-1):
    ans+=c(i,b)*c(h-i-1,w-b-2)
print(ans)

Submission status: Wrong Answer

Solution code:
N=2*10**5+3
mod=10**9+7
fac=[1]*(N+1)
for i in range(1,N+1):
    fac[i]=fac[i-1]*i%mod
inv_fac=[1]*(N+1)
inv_fac[N]=pow(fac[N],mod-2,mod)
for i in range(N-1,0,-1):
    inv_fac[i]=inv_fac[i+1]*(i+1)%mod
def nCr(n,r):
    if n<=0 or r<0 or r>n:
        return 0
    return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod

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

Submission status: Wrong Answer

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

import math

def f(n):
  a1 = pow(math.factorial(B + n + H - A - 1), 1, 10**9+7)
  a2 = pow(math.factorial(W - B - 1 - n + A - 1), 1, 10**9+7)
  b1 = pow(math.factorial(B + n) % (10**9 + 7), 1, 10**9+7)
  b2 = pow(math.factorial(H - A - 1) % (10**9 + 7), 1, 10**9+7)
  b3 = pow(math.factorial(W - B - 1 - n) % (10**9 + 7), 1, 10**9+7)
  b4 = pow(math.factorial(A - 1) % (10**9 + 7), 1, 10**9+7)
  return int(a1 * a2 / b1 / b2 / b3 / b4)

def sigma(func, frm, to):
  result = 0
  for i in range(frm, to+1):
    result += func(i)
  return result

print(sigma(f, 0, W-B-1))

Submission status: Wrong Answer

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

import math

def f(n):
  a1 = math.factorial(B + n + H - A - 1) % (10**9 + 7)
  a2 = math.factorial(W - B - 1 - n + A - 1) % (10**9 + 7)
  b1 = math.factorial(B + n) % (10**9 + 7)
  b2 = math.factorial(H - A - 1) % (10**9 + 7)
  b3 = math.factorial(W - B - 1 - n) % (10**9 + 7)
  b4 = math.factorial(A - 1) % (10**9 + 7)
  return int(a1 * a2 / b1 / b2 / b3 / b4)

def sigma(func, frm, to):
  result = 0
  for i in range(frm, to+1):
    result += func(i)
  return result

print(sigma(f, 0, W-B-1))

Submission status: Wrong Answer

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

import math

def f(n):
  a1 = math.factorial(B + n + H - A - 1) % (10**9 + 7)
  a2 = math.factorial(W - B - 1 - n + A - 1) % (10**9 + 7)
  b1 = math.factorial(B + n) % (10**9 + 7)
  b2 = math.factorial(H - A - 1) % (10**9 + 7)
  b3 = math.factorial(W - B - 1 - n) % (10**9 + 7)
  b4 = math.factorial(A - 1) % (10**9 + 7)
  return a1 * a2 / b1 / b2 / b3 / b4

def sigma(func, frm, to):
  result = 0
  for i in range(frm, to+1):
    result += func(i)
  return result

print(sigma(f, 0, W-B-1))

Submission status: Wrong Answer

Solution code:
h,w,a,b=map(int,input().split())
mod=10**9+7
ans=0
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 = h+w+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

#a = cmb(n,r,mod)
for i in range(h-a):
    p=(i+1)+(b-1)
    q=(h-i-1)+((w-b)-1)
    ans+=cmb(p,i+1,mod)*cmb(q,h-i-1,mod)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.misc import comb
H,W,A,B=map(int,input().split())
p=0
for i in range(B+1,W+1):
    p+=comb(H-A+i,i,exact=True)*comb(W-i+1+A,A,exact=True)
k=p%1000000007
print(k)

Submission status: Wrong Answer

Solution code:
# 0<=y<h-bなるyを通るとこからゴールの右下までのnCrをする
# グリッドじゃなくてマス目にしただけでnCrわからなくなるの、あたまが弱すぎる
h, w, a, b = map(int, input().split())
ans = 0


def ncr(n, r):
    res = 1
    for i in range(1, r + 1):
        res = res * (n - i + 1) // i
    return res


print(ncr(h + w, h))

for y in range(1, h - b + 1):
    ans += ncr(y, a) * ncr(w - a - 1 + h - b, w - a)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions 
H,W,A,B=map(int,input().split())
mod =10**9+7
def C(n,m):
    if n*m==0:
        C =1
    else:
        bunbo=[0]*min(m,n)
        bunsi=[0]*min(m,n)
        for k in range(min(m,n)):
            bunbo[k]=min(m,n)-k
            bunsi[k]=n+m-k
        for k in range(min(m,n)):
            for j in range(min(n,m)):
                if fractions.gcd(bunsi[j],bunbo[k])==0:
                    gcd =fractions.gcd(bunsi[j],bunbo[k])
                    bunsi[j]=bunsi[j]//gcd
                    bunbo[k]=bunbo[k]//gcd
                if bunbo[k]==1:
                    break   
        C=1
        for k in range(min(n,m)):
            C=C*bunsi[k]%mod
    return C
Total = C(H-1,W-1)
dame = 0
for k in range(B):
    dame += C(k,H-A-1)*C(W-1-k,A-1)
answer = (Total-dame)%mod
print(answer)

Submission status: Wrong Answer

Solution code:
H,W,A,B=map(int,input().split())
def kumi(h,w,a):
    a[0]=1
    #print(a)
    for i in range(1,h):
        a[i]=a[i-1]*(i-1+w)//i%(10**9+7)
        #print(a)
    return a
f=[0]*(H-A)
s=[0]*(H)
f=kumi(H-A,B,f)
s=kumi(H,W-B,s)
#print(f)
#print(s)
ans=0
for i in range(H-A):
    ans+=f[i]*s[-i-1]
print(ans%(10**9+7))

Submission status: Wrong Answer

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

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

#以下、引数にnCrのnに相当する数を入れる。
factorials, invs = prepare(H+W,MOD)
#以下でnCrのMODを求める。
ans = 0
#x = W - B - 1
for b in range(B,W):
  #if i == 0:
  #  ans += (factorials[H-A-1+B] * invs[H-A-1] % MOD * invs[B] % MOD) * (factorials[A+W-B] * invs[A] % MOD * invs[W-B] % MOD) % MOD
  #else:
  #  ans += ((factorials[H-A-1+B+i] * invs[H-A-1] % MOD * invs[B+i] % MOD) - (factorials[H-A-1+B+i-1] * invs[H-A-1] % MOD * invs[B+i-1] % MOD)) * (factorials[A+W-B-i] * invs[A] % MOD * invs[W-B-i] % MOD) % MOD
  ans += ((factorials[H-A-1+b] * invs[H-A-1] % MOD * invs[b] % MOD) * (factorials[A-1+W-b-1] * invs[A-1] % MOD * invs[W-b-1] % MOD)) % MOD
print(ans)

Submission status: Wrong Answer

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

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

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  if n == 0 and k == 0:
    return 0
  return fact[n] * rfact[k] * rfact[n-k] % mod 
ans = 0
for i in range(b,w):
  ans = (ans + comb(h-a-1+i,i) * comb(w-i+a-2,a-1)) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from array import *
import time
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = max(h+w-a-1, a+w)

s = time.time()


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
f = array('q', f)
ivf = [0] * MAX
ivf = array('q', ivf)
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))
e = time.time()
print(e - s)

Submission status: Wrong Answer

Solution code:
# # import numpy as np
# # import math
# # import sys
# # sys.float_info.max
# # H, W, A, B = map(int, input().split())
# # StoB = np.zeros(B)
# # BtoE = np.zeros(B)
# # sum = 0
# # all = math.factorial(H + W - 2) / (math.factorial(H - 1) * math.factorial(W - 1))
# # all = all % (10 ** 9 + 7)
# # for i in range(B):
# #     StoB[i] = math.factorial((i) + (H - A - 1)) / (math.factorial(i) * math.factorial(H - A - 1))
# #     BtoE[i] = math.factorial((W - i) + A - 2) / (math.factorial(W - i - 1) * math.factorial(A - 1))
# #     sum += StoB[i] * BtoE[i]
# # print(int(all - sum) % (10 ** 9 - 7))

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

#前計算 f[i] = i!
f = [1]
# print(f)
for i in range(H + W):
    f.append(f[i] * (i + 1) % mod)
# print(f)

def comb(n, r, p):
    print('n = ' + str(n))
    print('r = ' + str(r))
    # print(f[n])
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p
ans = 0
for i in range(W-B+1):
    print('i = ' + str(i))
    ans += comb(H-A+B+i, H-A, mod) * comb(A+W-B-i, A, mod) % mod
    print('ans = ' + str(ans))
print(ans % mod)

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

# #前計算　f[i] = i!
# f=[1]
# for i in range(h+w):
#   f.append(f[i]*(i+1)%mod)

# #C(n,r,p) = ( n! * r!^(p-2) * (n-r)!^(p-2) )%p
# #pythonだとpow()で二分累乗法が使える
# def comb(n, r, p):
#   return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p) % p

# #紫点ごとに調べる
# ans=0
# for i in range(b, w):
#   ans+= comb(h+i-a-1, i, mod) * comb(w-1-i+a-1, a-1, mod) % mod

# print(ans%mod)

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())
mod=10**9+7
N=H+W+1
bikkuri=[0 for i in range(N)]
bikkuri[0]=1
for i in range(1,N):
    bikkuri[i] = (i * bikkuri[i-1])%mod
gyaku=[0 for i in range(N)]
gyaku[0]=1
for i in range(1, N):
    gyaku[i]=pow(bikkuri[i], mod-2, mod)
def comb(n,r):
    return bikkuri[n]*gyaku[n-r]*gyaku[r]%mod
def homb(n,r):
    return comb(n+r,r)%mod
dame = []
for i in range(B):
    dame.append(homb(H-A-1, i) * homb(W-1-i,A-1))
ans = homb(W-1, H-1) - sum(dame)

Submission status: Wrong Answer

Solution code:
H, W, A, B = list(map(int, input().split()))
bikkuri=[1]
mod = 10**9 + 7
for i in range(1, H+W):
        bikkuri.append((i * bikkuri[i-1])%mod)
def comb(n, r):
    return round(bikkuri[n] / (bikkuri[n-r] * bikkuri[r]))
dame = []
for i in range(B):
    dame.append(comb(H-A-1+i, i)%mod * comb(W-1-i+A-1,A-1)%mod)
ans = comb(W-1+H-1, H-1)%mod - sum(dame)
print(ans%mod)