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:
h, w, a, b = map( int, input().split() )

SIZE = h+w+2
MOD = 10**9 + 7
MOD_Farmer = 10**9+5

fact = [0] * SIZE
inv = [0] * SIZE
fact_inv = [0] * SIZE

# prepare --------------------------------
inv[0] = 0
inv[1] = 1
fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
for i in range( 2, SIZE ):
  fact[i] = fact[i-1] * 2 % MOD
  fact_inv[i] = fact[i] **( 10**4 ) \
              * fact[i] **( 10**5 ) \
              * fact[i] ** 5 % MOD % MOD
# ----------------------------------------
def comb( n, r ):
  if r >= 0 and n >= 0:
    return fact[n] * fact_inv[n-r]%MOD * fact_inv[r]%MOD
  else :
    return 0.0
# ----------------------------------------

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

Submission status: Wrong Answer

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

SIZE = h+w+2
MOD = 10**9 + 7
MOD_Farmer = 10**9+5

fact = [0] * SIZE
inv = [0] * SIZE
fact_inv = [0] * SIZE

# prepare --------------------------------
inv[0] = 0
inv[1] = 1
fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
for i in range( 2, SIZE ):
  fact[i] = fact[i-1] * 2 % MOD
  fact_inv[i] = fact[i] **( 10**4 ) \
              * fact[i] **( 10**5 ) \
              * fact[i] ** 5 % MOD % MOD
# ----------------------------------------
def comb( n, r ):
  if r >= 0 and n >= 0:
    return fact[n] * fact_inv[n-r] * fact_inv[r]
  else :
    return 0.0
# ----------------------------------------

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jul 26 05:23:03 2019

@author: matsui
"""

import numpy as np

def kai(a,b):
    ans=int(1)
    for i in range(a,b-1,-1):
        ans*=int(i)
        if ans > 1e15: ans=int(ans%(1e9+7))
    
    return int(ans)

def C(a,b):
    #x=np.arange(b+1,a+1)
    #y=np.arange(1,(a-b)+1)
    ans = kai(a,(b+1))/kai((a-b),1)
    return int(ans%(1e9+7))

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

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

Submission status: Wrong Answer

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

@lru_cache(maxsize=200000)
def func(i, j) :
    if j == 0 :
        return 1
    else :
        return func(i, j-1)*(i+j)//j%(10**9+7)
ha_w = [func(h-a-1, i) for i in range(w)]
a_wb = [func(a-1, i) for i in range(w-b)]
ans = sum([ha_w[-1-i]*a_wb[i]%(10**9+7) for i in range(w-b)])%(10**9+7)
print(ans)

Submission status: Wrong Answer

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

	def my_pow(x, n):
		ans = 1
		while n > 0:
			if (n&1) == 1:
				ans = ans*x%DIV
			x = x*x%DIV
			n >>= 1
		return ans%DIV

	fact = [0]*(H+W+1)
	inverse = [0]*(H+W+1)
	inverse[0] = 1
	fact[0] = 1

	for i in range(1, H+W-A+1):
		fact[i] = (fact[i-1]*i%DIV)
		inverse[i] = my_pow(fact[i], DIV-2)%DIV

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

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

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

	def my_pow(x, n):
		ans = 1
		while n > 0:
			if (n&1) == 1:
				ans = ans*x%DIV
			x = x*x%DIV
			n >>= 1
		return ans%DIV

	fact = [0]*(H+W+1)
	inverse = [0]*(H+W+1)
	inverse[0] = 1
	fact[0] = 1

	for i in range(1, H+W-A+1):
		fact[i] = (fact[i-1]*i%DIV)
		inverse[i] = my_pow(fact[i], DIV-2)%DIV

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

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

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
def p(x,y):
  if x==0 or y==0: a=0
  elif x==1 or y==1: a=1
  else: a=math.factorial(x+y-2)//math.factorial(x-1)//math.factorial(y-1)
  return a
n=0
for i in range(h-a):
  n+=(p(i+1,b)*p(h-i,w-b))%(10**9)+7
n%=(10**9)+7
print(int(n))

Submission status: Wrong Answer

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
import functools
import operator
def p(x,y):
  if x==0 or y==0: return 0
  elif x==1 or y==1: return 1
  if x>=y: 
    k=x-1
    l=y-1
  else:
    k=y-1
    l=x-1
  return functools.reduce(operator.mul, [(k-i)//(l-i) for i in range(l)])
n=sum([p(i+1,b)*p(h-i,w-b) for i in range(h-a)])%(10**9)+7
print(int(n))

Submission status: Wrong Answer

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
import functools
import operator
def p(x,y):
  if x==0 or y==0: return 0
  elif x==1 or y==1: return 1
  if x>=y: 
    k=x-1
    l=y-1
  else:
    k=y-1
    l=x-1
  return functools.reduce(operator.mul, [(k-i)//(l-i) for i in range(l)])
n=sum([p(i+1,b)*p(h-i,w-b) for i in range(h-a)])//(10**9)+7
print(int(n))

Submission status: Wrong Answer

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

field = [[1 for i in range(W)] for i in range(H)]
for i in range(H-A-1,H):
    for j in range(0,B):
        field[i][j]=0
for i in range(1,H):
    if i < H-A:
        for j in range(1,W):
            field[i][j]=field[i][j-1]+field[i-1][j]
    else:
        for j in range(1,W):
            if j > B-1:
                field[i][j]=field[i][j-1]+field[i-1][j]
print(field[H-1][W-1]%(10**9+7))

Submission status: Wrong Answer

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

field = [[1 for i in range(W)] for i in range(H)]
for i in range(H-A-1,H):
    for j in range(0,B):
        field[i][j]=0
for i in range(1,H):
    if i < H-A:
        for j in range(1,W):
            field[i][j]=field[i][j-1]+field[i-1][j]
    else:
        for j in range(1,W):
            if j > B-1:
                field[i][j]=field[i][j-1]+field[i-1][j]
print(field[H-1][W-1])

Submission status: Wrong Answer

Solution code:
def comb(a, b):
  b = min(b, a - b)
    
  if b == 0:
    return 1
  
  f = 1
  for i in range(1, b + 1):
    f *= a + 1 - i
    f //= i
    f = f % (10**9+7)
  return f

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


c = min(h - a - 1, w - b - 1)

ans = 0
#print(c)


#a1 = comb(b + h - a - 1, h - a - 1)
#a2 = comb(w - b - 1 + a, a)

for i in range(c + 1):
  #print("a1 = {}_C_{}".format(b + h - a - 1,h - a - 1 - i))
  #print("a2 = {}_C_{}".format(w - b - 1 + a, a + i))
  
  if i == 0:
    a1 = comb(b + h - a - 1, h - a - 1 - i)
    a2 = comb(w - b - 1 + a, a + i)
  else:
#    a1 = a1 * (b + h - a - 1 - (h - a - 1 - i - 1)) // h - a - 1 - i
#    a2 = a2 * (w - b - 1 + a - (a + i - 1)) // a + i
    #print("i=",i, (h - a - i) , "//", (b + h - a - 1) - (h - a - 1 - i) + 1)
    #print("i=",i, (w - b - i) , "//", (a + i))
    #print(" a1: i={} {}/{}".format(i, h - a - i, b + i))
    #print(" a2: i={} {}/{}".format(i, w - b - i, a + i))
    a1 = a1 * (h - a - i) // (b + i)
    a2 = a2 * (w - b - i) // (a + i)
  #print("  a1={} a2={}".format(a1, a2))

  ans +=  a1 * a2
print(ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
import math

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

def route(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

ans = 0

for i in range(B, W):
    h1 = H-1-A      
    w1 = i        
    h2 = A-1        
    w2 = W-1-i      
    
    ans += route(h1+w1, w1) * route(h2+w2, w2) % mod

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from numpy import array
from math import factorial
h,w,a,b=map(int,input().split())
h-=1
w-=1
a-=1
b-=1
mod=10**9+7
table=[factorial(i)%mod for i in range(h+w+1)]
def cmb(a,b):
    return table[a]//table[a-b]//table[b]
migisita=[cmb(i+h-a-1,h-a-1)for i in range(b+1,w+1)]
hidarisita=[cmb(a+i-1,i-1)for i in range(1,w-b+1)][::-1]
print(sum(array(hidarisita)*array(migisita)))

Submission status: Wrong Answer

Solution code:
from sys import exit
H,W,A,B = [int(n) for n in input().split()]
MOD = 10**9+7
# N = int(input())
# a = [int(input()) for _ in range(N)]
# S = str(input())
# L = len(S)
# T = str(input())
# exit()
# print(H,W,A,B)
def modfact(n, m):
    res=1
    for i in range(2,n+1):
        res*=i
        res%=m
    return res

def modinv0(a, m):
    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
ans=0
for i in range(B,W):
    # print(i,H-A-1)
    deno = modfact(i,MOD) * modfact(H-A-1,MOD)
    nume = modfact(i+H-A-1,MOD)
    tmp = nume * modinv0(deno, MOD) %MOD

    # print(W-i-1, A-1)
    deno = modfact(W-i-1,MOD) * modfact(A-1,MOD)
    nume = modfact(W-i-1+A-1,MOD)
    tmp *= nume * modinv0(deno, MOD) %MOD
    ans += tmp
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,a,b=map(int,input().split())
l=[[0 for i in range (w)] for j in range (h)]
for i in range(w):
    l[0][i]=1
for i in range(h-a):
    l[i][0]=1
for i in range(1,h-a):
    for j in range(1,w):
        l[i][j]=l[i-1][j]+l[i][j-1]
for i in range(h-a,h):
    l[i][b]=l[h-a-1][b]
for i in range(h-a,h):
    for j in range(b+1,w):
        l[i][j]=l[i-1][j]+l[i][j-1]
print(l[h-1][w-1]/(10**9+7))

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

def C(n, r):
	return factorial[n] * (x_inv[r] * x_inv[n-r] % mod) % mod

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

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

# x_inv = []
# for i in range(H+W):
# 	x_inv.append(power(factorial[i], mod-2))

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

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

Submission status: Wrong Answer

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

# 事前計算 + 演算ごとに mod する
def solve():
    # 組合せの計算用に階乗を事前計算しておく
    MOD = 10 ** 9 + 7
    FACT = [0] * (H + W + 1)
    INV_FACT = [0] * (H + W + 1)  # 逆元. 組合せの計算ごとにMODを取るため

    FACT[0], INV_FACT[0] = 1, 1
    for i in range(1, (H + W + 1)):
        FACT[i] = (FACT[i - 1] * i) % MOD
        INV_FACT[i] = pow(FACT[i], MOD - 2, MOD)  # フェルマーの小定理を使う

    def mod_nCr(n, r):
        if n < r or n == 0 or r == 0:
            return 1

        return FACT[n] * (INV_FACT[r] * INV_FACT[n - r]) % MOD

    # print(H, W, A, B)

    # 座標は(x, y). startは(0, 0)
    goal = W - 1, H - 1

    # 境界点: 移動できないエリアの右上の点
    nx = B - 1
    ny = H - A

    # 境界点から右斜め上に1つ移動した点(choke_left)から, 右端へ伸びる線がchoke points
    choke_left = nx + 1, ny - 1

    choke_points = []
    for i in range(B, W):
        choke_points.append((i, choke_left[1]))

    # 組合せを計算する: startからcp1, cp2からgoalまで組合せを掛ける
    ans = 0
    for cp1 in choke_points:
        x, y = cp1
        from_start_to_cp1 = mod_nCr(x + y, x)

        # cp1から1つ下の点がcp2
        y += 1
        dx, dy = goal[0] - x, goal[1] - y
        from_cp2_to_goal = mod_nCr(dx + dy, dx)

        ans = ans % MOD + (from_start_to_cp1 * from_cp2_to_goal % MOD) % MOD

    return ans

res = solve()
print(res)

Submission status: Wrong Answer

Solution code:
H,W,A,B=map(int,input().split())
memo=[[1 for j in range(W)] for i in range(H)]
for i in range(1,H):
	for j in range(W):
		if i>=H-A and j <B:
			memo[i][j]=0
		elif j!=0:	memo[i].append((memo[i-1][j]+memo[i][j-1])%(10**9+7))
print(memo[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())
A = H - A
B -= 1
#init 2d list
dp = [[0 for w in range(W)] for h in range(H)]
#assign 1 to 0 row and column
dp[0] = [1 for w in range(W)]
for h in range(0, H):
    for w in range(0, W):
        if w <= B and h >= A:
            dp[h][w] = 0
        else:
            dp[h][w] = (dp[h][w - 1] + dp[h - 1][w])
print(dp[-1][-1])

Submission status: Wrong Answer

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

n=h+w+1
fc,inv=[1]*n,[1]*n
for i in range(1,n):
    fc[i]=i*fc[i-1]%mod
inv[n-1]=pow(fc[n-1],mod-2,mod)
for i in range(n-1,0,-1):
    inv[i-1]=inv[i]*i%mod
f=lambda a,b:fc[a+b]*inv[a]*inv[b]%mod

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

Submission status: Wrong Answer

Solution code:
import math
from itertools import combinations
from collections import Counter


def solve(H, W, A, B):
    ans = 0
    R = 10 ** 9 + 7

    p1_y = math.factorial(H - 1 - A)
    d2_y = math.factorial(H - 1 - (H - A))
    way1 = -1
    way3 = -1

    for i in range(0, W - B):
        p1 = (B + i, H - 1 - A)
        p2 = (B + i, H - A)
        e = (W - 1, H - 1)
        d2 = (e[0] - p2[0], e[1] - p2[1])

        if way1 == -1:
            way1 = (math.factorial(p1[0] + p1[1]) // math.factorial(p1[0]) // p1_y)
        else:
            way1 *= (p1[0] + p1[1])
            way1 //= (p1[0])

        if way3 == -1:
            way3 = (math.factorial(d2[0] + d2[1]) // math.factorial(d2[0]) // d2_y)
        else:
            way3 *= (d2[0] + 1)
            way3 //= (d2[0] + d2[1] + 1)
        ans += way1 * way3
        way1 %= R
        way3 %= R
    return ans % R

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

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
fac = [1 for _ in range(10**6+1)]
for i in range(1, 10 **6):
    fac[i+1] = fac[i] * (i + 1) % mod

def combination(n, r):
    result = fac[n] // (fac[r] * fac[n-r]) % mod
    return result

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

Submission status: Wrong Answer

Solution code:
mod = 7+10**9
H,W,A,B=map(int,input().split())
def con(a,b):
    if b==0:return 1
    if a==b:return 1
    x=1
    for i in range(b):
        x=(x*(a-i)/(i+1))%mod
    x=int(x)
    return x

def calc(x,y):
    res = con(x+y-2,x-1)
    return res

all = 0
for i in range(W-B):
    x=i+1
    k = (calc(B+x,H-A)*calc(A,W-B-i))%mod
    all=int((all+k)%mod)
print(all)

Submission status: Wrong Answer

Solution code:
mod = 7+10**9
H,W,A,B=map(int,input().split())
def con(a,b):
    x=1
    for i in range(b):
        x=(x*(a-i)/(i+1))%mod
    x=int(x)
    return x

def calc(x,y):
    res = con(x+y-2,x-1)
    return res

all = calc(H,W)
for i in range(B):
    x=i+1
    k = (calc(x,H-A)*calc(A,W-i))%mod
    all=int((all-k)%mod)
print(all)

Submission status: Wrong Answer

Solution code:
import math
f = math.factorial
MOD = 1000000007
H, W, A, B = map(int, input().split())
# 左上(H-A, B) -> 右上(H-A, W-B)、右下(A, W-B)
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1

def debug(dp):
    return
    print('--')
    for row in dp:
        print(' '.join('{:10d}'.format(c) for c in row))

def pattern(w, h):
    return f(w + h - 2) // f(w - 1) // f(h - 1)

for y in range(0, H - A):
    dp[y][B - 1] = pattern(y + 1, B)
debug(dp)

for x in range(B, W):
    for y in range(0, H - A):
        dp[H - A][x] += dp[y][B - 1] * pattern(H - A - y, x - B + 1)
debug(dp)

if H - 1 > H - A:
    for x in range(B, W):
        dp[H - 1][W - 1] += dp[H - A][x] * pattern(A, W - x)
debug(dp)
print(dp[H - 1][W - 1] % MOD)

if False:
    # naive.
    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1
    for k in range(1, H + W):
        for y in range(max(H, W)):
            x = k - y
            if 0 <= y < H and 0 <= x < W:
                if y < H - A or B <= x:
                    if x - 1 >= 0:
                        dp[y][x] += dp[y][x - 1]
                    if y - 1 >= 0:
                        dp[y][x] += dp[y - 1][x]
    debug(dp)

Submission status: Wrong Answer

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

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * N
inv = [1] * N

# 階乗
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 
# 普通の逆元テーブル
for i in range(1, N):
    inv[i] = pow(i, MOD-2, MOD)
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

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

Submission status: Wrong Answer

Solution code:
# calculate N!(modP)
def fac(n):
    ans = 1
    mod = 10**9+7
    for i in range(1, n+1):
        ans *= i
        ans %= mod
    return ans
 
# calculate a**b(modP)     
def cal(a, b, mod):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return cal(a, b//2, mod)**2 % mod
    else:
        return (a * cal(a, b-1, mod)) % mod 
    
H, W, A, B = map(int, input().split())

ans = 0
mod = 10**9+7


for w in range(B, W):
    now = fac((H-A-1)+w) * cal(fac(H-A-1), mod-2, mod) * cal(fac(w), mod-2, mod) % mod
    now *= fac((A-1)+(W-w-1)) * cal(fac(A-1), mod-2, mod) * cal(fac(W-w-1), mod-2, mod)
    ans += now
print(ans)

Submission status: Wrong Answer

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

# 組み合わせの数だけ返してくれる関数
def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator
    
H,W,A,B = map(int, input().split())

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans += nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h) % (10 ** 9 + 7)
    h -= 1
    w += 1

print(ans)

Submission status: Wrong Answer

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

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, w+h+5):
    fac.append(fac[i-1] * i % m)
    inv.append(m - inv[m%i] * (m/i) % m)
    finv.append(finv[i-1] * inv[i] % m)

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


row = []
for i in range(h-a):
    row.append(nck(b+i, i))

ans = 0
for i in range(len(row)-1):
    ans += row[i] * nck(w-b-2 + h-1-i, h-1-i)
    ans %= m

ans += row[-1] * nck(w-b-1 + a, a)
ans %= m

print(ans)

Submission status: Wrong Answer

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

f = []
F = 1
f.append(F)
for i in range(1, w+h+1):
    F *= i
    F %= m
    f.append(F)

def permutations_count(n, r):
    return f[n] // f[n-r] // f[r]

row = []
for i in range(h-a):
    row.append(permutations_count(b+i, i))

ans = 0
for i in range(len(row)-1):
    ans += row[i] * permutations_count(w-b-2 + h-1-i, h-1-i)
    ans %= m

ans += row[-1] * permutations_count(w-b-1 + a, a)
ans %= m

print(ans)

Submission status: Wrong Answer

Solution code:
# E.py#
#K, N = map(int,input().split())
P = 10**9+7
H, W, A, B = map(int,"10 7 3 4".split())

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)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def fact(i):
	t = 1
	while i > 0:
		t = (t * i) % P
		i -= 1
	return t

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
from math import factorial
h, w, a, b = list(map(int, input().split()))
num_path = 0

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

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

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
from math import factorial
h, w, a, b = list(map(int, input().split()))
num_path = 0

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

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

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

Submission status: Wrong Answer

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

def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = m * (n - i + 1) / i
    return m

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

# http://gzlku.hatenablog.com/entry/2017/09/17/074653
r = 0
for i in range(H-A):
    combination = comb(B - 1 + i, B - 1) * comb((W - B - 1) + (H - i - 1), W - B - 1)
    r += combination % (10e9 + 7)

print(r)

Submission status: Wrong Answer

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

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

# 初期化
# W行 H列
mat = [[0 for x in range(W)] for y in range(H)]

# AかつBに−１を代入
for y in range(H - A, H):
    for x in range(0, B):
        mat[y][x] = -1

# 歩ける数を代入
for y in range(H):
    for x in range(W):
        # 右端でも左端でもない
        if (x != W - 1) and (y != H - 1):
            # 右が空
            if mat[y][x + 1] == 0:
                mat[y][x] += 1
            # 下が空
            if mat[y + 1][x] == 0:
                mat[y][x] += 1
        # 右端のみ
        elif (x == W - 1) and (y != H - 1):
            # 下が空
            if mat[y + 1][x] == 0:
                mat[y][x] += 1
        # 下端のみ
        elif (x != W - 1) and (y == H - 1):
            # 右が空
            if mat[y][x + 1] == 0:
                mat[y][x] += 1

# ゴールまでのパターン数を計算
cnt = 0
for y in range(H):
    for x in range(W):
        if mat[y][x] == 2:
            cnt += 1
pattern_num = 2 ** cnt
print(pattern_num)

Submission status: Wrong Answer

Solution code:
h,w,a,b = map(int,input().split())
dp = [[0 for _ in range(w)] for __ in range(h)]
dp[0] = [1 for i in range(w)]
mod = 10**9 + 7
for i in range(1,h):
  for j in range(w):
    if h-i <= a and j <= b-1:
      continue
    if j == 0:
      dp[i][j] = dp[i][j-1] % mod
    else:
      dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % mod
print(dp[h-1][w-1])

Submission status: Wrong Answer

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(w-i-2+a, w-i-1)%MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
def main():
    """
    入力例2: 10 7 3 4
    S......
    .......
    .......
    .......
    .......
    .......
    .......
    xxxx...
    xxxx...
    xxxx..G

    h-1,w-1だけ移動する
    全通り - NGパターン

    全通り:
        (h-1 + w-1) C (h-1)

    Sから左上のx(1)にたどり着くルート:
        (H-A) C (H-A) = 1
        (1)からゴールまでのルート: (A-1 + W-1) C (A-1)
    Sから左上のxの右x(2)にたどり着くルート:
        (H-A + 1) C (1) = H-A+1
        ※ただし(1)から右にいくルートを除く
            →xの直前から下に行く
        (2)からゴールまでのルート: (A-1 + W-2) C (A-1)
    """
    H, W, A, B = map(int, input().split())

    ans = TLE(H, W, A, B)
    print(ans)


def TLE(H, W, A, B):
    m = 10 ** 9 + 7
    a = ncr(H-1+W-1, min(H, W)-1)
    ans = a
    for i in range(B):
        x = ncr(H-A-1+i, H-A-1)
        y = ncr(A-1 + W-i-1, A-1)
        ans -= x * y

    return ans


def ncr(n, r):
    import math
    if n < r:
        return 0
    f = math.factorial
    # rまでの並べ方について,組合せなので1/r
    return f(n) // f(n - r) // f(r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
w, h, a, b=map(int,input().split())
# n!、1/(n!)の用意
fact = [1]*300000
invfact = [1]*300000
for i in range(2,300000):
    fact[i] = (fact[i-1] * i) % MOD
    # フェルマーの小定理
    invfact[i] = (invfact[i-1] * pow(i, MOD-2, MOD)) % MOD
def nCm(n,m):
    return (fact[n]*invfact[m]*invfact[n-m])%MOD
# (0,0)->(w-1,h-1)へ移動するものとして、
# (0,0)->(i,h-a-1)->(i,h-a)->(w-1,h-1)への移動を考える
ret = 0
for i in range(b, w):
    # 実際は前半×後半を足していくだけ
    # 前半は右にi、下にh-a-1
    # 後半は右にw-i-1、下にa-1移動
    ret += (nCm(i+h-a-1, i) * nCm(w+a-i-2, a-1))%MOD
print(ret%MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
w, h, a, b=map(int,input().split())
# n!、1/(n!)の用意
fact = [1]*300000
invfact = [1]*300000
for i in range(2,300000):
    fact[i] = (fact[i-1] * i) % MOD
    # フェルマーの小定理
    invfact[i] = (invfact[i-1] * pow(i, MOD-2, MOD)) % MOD
def nCm(n,m):
    return (fact[n]*invfact[m]*invfact[n-m])%MOD
# (0,0)->(w-1,h-1)へ移動するものとして、
# (0,0)->(i,h-a-1)->(i,h-a)->(w-1,h-1)への移動を考える
ret = 0
for i in range(b, w):
    # 実際は前半×後半を足していくだけ
    # 前半は右にi、下にh-a-1
    # 後半は右にw-i-1、下にa-1移動
    ret += nCm(i+h-a-1, i) * nCm(w+a-i-2, a-1)
print(ret%MOD)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
w, h, a, b=map(int,input().split())
# n!、1/(n!)の用意
fact = [1]*200000
invfact = [1]*200000
for i in range(2,200000):
    fact[i] = (fact[i-1] * i) % MOD
    # フェルマーの小定理
    invfact[i] = (invfact[i-1] * pow(i, MOD-2, MOD)) % MOD
def nCm(n,m):
    return (fact[n]*invfact[m]*invfact[n-m])%MOD
# (0,0)->(w-1,h-1)へ移動するものとして、
# (0,0)->(i,h-a-1)->(i,h-a)->(w-1,h-1)への移動を考える
ret = 0
for i in range(b, w):
    # 実際は前半×後半を足していくだけ
    # 前半は右にi、下にh-a-1
    # 後半は右にw-i-1、下にa-1移動
    ret += nCm(i+h-a-1, i) * nCm(w+a-i-2, a-1)
print(ret%MOD)

Submission status: Wrong Answer

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

p = 10 ** 9 + 7
s = 0

fact = [1]

for i in range(1, h+w-2):
    fact.append(fact[i-1] * i % p)

rfact = [(h+w-2) % p]

for i in range(h+w-1, 0, -1):
    rfact.append(rfact[-1] * i % p)

rfact.reverse()

def comb(n, r):
    return fact[n]//fact[n-r]%p//fact[r]%p

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

print(s%p)

Submission status: Wrong Answer

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

p = 10 ** 9 + 7
s = 0

fact = [1]

for i in range(1, h+w-2):
    fact.append(fact[i-1] * i % p)

rfact = [(h+w-2) % p]

for i in range(h+w-1, 0, -1):
    rfact.append(rfact[-1] * i % p)

rfact.reverse()

def comb(n, r):
    return fact[n]//fact[n-r]//fact[r]%p

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

print(s%p)

Submission status: Wrong Answer

Solution code:
import scipy.misc as scm

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

s = 0

for i in range(w-b):
    s += scm.comb(h+w-a-2-i, w-1-i, 1) * scm.comb(a-1+i, a-1, 1)

print(s)

Submission status: Wrong Answer

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

from math import factorial
H,W,A,B=map(int, input().split())
p=10**9+7
ans=0
X=[1]
Y=[1]
for i in range(H+W-2):
  fact=factorial(i+1)%p
  X+=[fact]
  Y+=[power_func( fact, p-2,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)

Submission status: Wrong Answer

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

from math import factorial
H,W,A,B=map(int, input().split())
p=10**9+7
ans=0
X=[1]
Y=[1]
for i in range(H+W-2):
  fact=factorial(i+1)%p
  X+=[fact]
  Y+=[power_func( fact, p-2,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)

Submission status: Wrong Answer

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

def comb(x,y):
  return(math.factorial(x)//(math.factorial(x-y)*math.factorial(y)))

alls=comb(H+W-2,W-1)
for i in range(B):
  alls-=comb(H-A-1+i,H-A-1)*comb(W+A-2-i,A-1)

print(alls)

Submission status: Wrong Answer

Solution code:
import math

def nCr(n, r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

def solv(H, W, A, B):
    D = 10**9 + 7
    h = H - 1
    w = W - 1

    total = nCr(h+w, h)

    i = h - A
    forbidden = 0
    for j in range(B):
        forbidden += nCr(i+j, i) * nCr((h-i-1)+(w-j), h-i-1)

    return int(total - forbidden) % D


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

res = solv(H, W, A, B)
print(res)