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:
def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
            result = result%inf
    return int(result)

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

inf = 10**9+7
key1, key2 = 1, nCr(h+w-b-2, h-1)
ans = key2%inf
for i in range(1, h-a):
    key = (key1*(b+i)//i)%inf
    key2 = (key2*(h-1-i+1)//(h+w-b-2-i+1))%inf
    ans = (ans+((key-key1))*key2)%inf
    key1 = key
print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7
flist = [1] * (h+w+1)
for i in range(1,h+w):
    flist[i] = (flist[i-1] * i)%mod

def cmb(n,r):
    return (flist[n]//(flist[r]*flist[n-r]))%mod

for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans = (ans+e)%mod

print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7
flist = [1] * (h+w+1)
for i in range(1,h+w):
    flist[i] = (flist[i-1] * i)%mod

def cmb(n,r):
    return (flist[n]//(flist[r]*flist[n-r]))%mod

for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans += e

print(ans)

Submission status: Wrong Answer

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

flist = [1 for _ in range(h+w)]
for i in range(1,h+w):
    flist[i] = flist[i-1] * i

def cmb(n,r):
    return flist[n]//(flist[r]*flist[n-r])

for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans += e

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

nums = input().split()
H = int(nums[0])
W = int(nums[1])
A = int(nums[2])
B = int(nums[3])
MX = max(H,W)
MN = min(H,W)
mod = 10**9 + 7



#全体
total = cmb(H+W-2,W-1)

#侵入不可
K = 1
forbidden = 0
while K < B + 1:
    x1 = cmb(H-A+K-2,K-1)
    x2 = cmb(W-K+A-2,A-1)

    x = x1 * x2
    forbidden += x
    
    x = 0
    x1 = 0
    x2 = 0
    K += 1

answer = int(total - forbidden)
print(answer % ((10 ** 9) + 7))

Submission status: Wrong Answer

Solution code:
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p
h,w,a,b=map(int,input().split())
mod=10**9+7
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+w-b,b+i,mod)*comb(w-b+a-1,a+i,mod)
print(t%mod)

Submission status: Wrong Answer

Solution code:
base = 10**9 + 7

def comb(x, y):#xCy = [x-1]C[y-1] * n / k
  res = 1
  for i in range(x):
    res = res * (x-i)
  for i in range(y):
    res = res // (y-i)
  return res % base

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

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

Submission status: Wrong Answer

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

f1 = [1 for i in range(W)]

for i in range(H-1): #f1 -> #f2
  f2 = [0 for j in range(W)]
  for j in range(W):
    if j == 0:
      f2[0] = f1[0]
    elif i > H-1-A and j<B:
      f2[j] = f1[j]
    else:
      f2[j] = f1[j] + f2[j-1]
  for j in range(W):
    f1[j] = f2[j]%base
print(f1[W-1])

Submission status: Wrong Answer

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

f1 = [0 for i in range(W)]

for i in range(H-1): #f1 -> #f2
  f2 = [0 for j in range(W)]
  for j in range(W):
    if j == 0:
      f2[0] = f1[0]
    elif i > H-1-A and j<B:
      f2[j] = f1[j]
    else:
      f2[j] = f1[j] + f2[j-1]
  for j in range(W):
    f1[j] = f2[j]%base
print(f2[W-1])

Submission status: Wrong Answer

Solution code:
def examD(mod):
    from operator import mul
    from functools import reduce
    def comb2(n, r):
        r = min(n - r, r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1, r + 1))
        return over // under

    H, W, A, B =LI()
    k = W-B
    ans = int(0)
    C1 = [0]*k; C2 = [0]*k
    C1[0] = comb2(H - A + B + 0 - 1, H - A - 1) % mod
    C2[0] = comb2(A + W - (B + 0) - 2, A - 1) % mod
    C2[k-1] = 1
    for i in range(1,k):
        C1[i] = (C1[i-1]*(H-A+B+i-1)//(B+i))%mod
    for i in range(k-1,1,-1):
        C2[i-1] = (C2[i]*(A+W-(B+i-1)-2))//(W-(B+i))%mod
    for i in range(k):
        ans = (ans+C1[i]*C2[i])%mod
    """
    for i in range(1,k):
        C1[i] = comb2(H - A + B + i - 1, H - A - 1) % mod
        C2[i] = comb2(A + W - (B + i) - 2, A - 1) % mod
        ans = (ans+C1[i]*C2[i])%mod
    """
    print(ans)
#    print(C1)
#    print(C2)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

examD(mod)

Submission status: Wrong Answer

Solution code:
H,W,A,B = map(int, input().split())                                             
                                                                                
dp = [[0 for w in range(W)] for h in range(H)]                                  
                                                                                
                                                                                
MOD = 10 ** 9 + 7                                                               
for w in range(W):                                                              
    dp[0][w] = 1                                                                
for h in range(H-A):                                                            
    dp[h][0] = 1                                                                
for h in range(1, H-A):                                                         
    for w in range(1,W):                                                        
        dp[h][w] = dp[h-1][w] % MOD + dp[h][w-1] % MOD                          
for h in range(H-A, H):                                                         
    for w in range(B,W):                                                        
        dp[h][w] = dp[h-1][w] % MOD + dp[h][w-1] % MOD                          
print(dp[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())                                          
                                                                                
MOD = 10**9+7                                                                   
                                                                                
path = [[0 for w in range(W)] for h in range(H)]                                
for w in range(W):                                                              
    path[0][w] = 1                                                              
for h in range(H-B):                                                            
    path[h][0] = 1                                                              
                                                                                
for h in range(1, H-B):                                                         
    for w in range(1, W):                                                       
        path[h][w] = path[h-1][w]%MOD + path[h][w-1]%MOD                        
                                                                                
for h in range(1, H):                                                           
    for w in range(A, W):                                                       
        path[h][w] = path[h-1][w]%MOD + path[h][w-1]%MOD                        
                                                                                
print(path[H-1][W-1])

Submission status: Wrong Answer

Solution code:
H, W, A, B = map(int, input().split())                                          
                                                                                
path = [[0 for w in range(W)] for h in range(H)]                                
for w in range(W):                                                              
    path[0][w] = 1                                                              
for h in range(H-B):                                                            
    path[h][0] = 1                                                              
                                                                                
for h in range(1, H-B):                                                         
    for w in range(1, W):                                                       
        path[h][w] = path[h-1][w] + path[h][w-1]                                
                                                                                
for h in range(1, H):                                                           
    for w in range(A, W):                                                       
        path[h][w] = path[h-1][w] + path[h][w-1]                                
                                                                                
print(path[H-1][W-1])

Submission status: Wrong Answer

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

import pdb
import sys
F = sys.stdin
H, W, A, B = F.readline().rstrip().split()
H = int(H)
W = int(W)
A = int(A)
B = int(B)
LL = 1e9 + 7

l = [[0] * W] * H
l[0] = [1] * W
for i in range(1, H - A):
    for j in range(W):
        if j == 0:
            l[i][j] = 1
            continue
        l[i][j] = l[i - 1][j] + l[i][j - 1]

for k in range(H - A, H):
    for m in range(B, W):
        if m == B:
            l[k][m] = l[k-1][m]
            continue
        l[k][m] = l[k-1][m] + l[k][m-1]

ans = int(l[H-1][W-1] % LL)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
H, W, A, B = map(int,input().split())
def f(a,b):
    p = math.factorial(a+b-2)
    q = math.factorial(a-1)
    r = math.factorial(b-1)
    S = p // (q*r)
    return S
T = 0
for i in range(1,B+1):
    P = f(H-A,i)
    Q = f(A,W-i+1)
    T = T + P*Q
R = f(H,W) - T
ans = R % (10**9+7)

Submission status: Wrong Answer

Solution code:
import math
H, W, A, B = map(int,input().split())
def f(a,b):
    p = math.factorial(a+b-2)
    q = math.factorial(a-1)
    r = math.factorial(b-1)
    S = p // (q*r)
    return S
T = 0
for i in range(1,B+1):
    P = f(H-A,i)
    Q = f(A,W-i+1)
    T = T + P*Q
R = f(H,W) - T
print(R)

Submission status: Wrong Answer

Solution code:
import math;

H, W, a, b = map(int, input().split(' '))
# 中継地点への行き方 * 中継地点からの行き方 ⇛各中継地点をたす
ans = 0
# 中間地点へのX、中間地点からのX
sgx = b - 1
gx = W - b - 1
sgxp = math.factorial(sgx)
gxp = math.factorial(gx)
sgyl = H - a


for i in range(sgyl):
    tmp1 = 1
    sgy = i
    sxy = sgx + sgy

    # for( n = sxy ; sgx != n; n--):
    aaa = math.factorial(sxy)
    bbb= math.factorial(sgy)
    tmp1 = aaa // (bbb*sgxp)

    gy = H -1 - i
    sxy = gy + gx
    aaa = math.factorial(sxy)
    bbb= math.factorial(gy)
    tmp2 = aaa // (bbb*gxp)
    ans = ans + tmp1*tmp2

b = ans % 100000007
print(int(b))

Submission status: Wrong Answer

Solution code:
import math;

H, W, a, b = map(int, input().split(' '))
# 中継地点への行き方 * 中継地点からの行き方 ⇛各中継地点をたす
ans = 0
# 中間地点へのX、中間地点からのX
sgx = b - 1
gx = W - b - 1
sgxp = math.factorial(sgx)
gxp = math.factorial(gx)
sgyl = H - a


for i in range(sgyl):
    tmp1 = 1
    sgy = i
    sxy = sgx + sgy

    # for( n = sxy ; sgx != n; n--):
    for n in range(sgx):
        tmp1 = tmp1 * (sxy - n)

    tmp1 = tmp1 // sgxp

    gy = H - i
    sxy = gy + gx -1
    tmp2 = 1
    for n in range(gx):
        tmp2 = tmp2 * (sxy - n)

    tmp2 = tmp2 // gxp
    ans = ans + tmp1*tmp2

b = ans % 100000007
print(int(b))

Submission status: Wrong Answer

Solution code:
# D　イロハちゃんと升目
cnt=0
h,w,a,b=map(int,input().split())
def find_power(n):
    # 0!からn!までのびっくりを出してくれる関数
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(10**9+7)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

powlist=find_power(h+w+1)
invlist=find_inv_power(h+w+1)
def combi(n,r):
    a=powlist
    b=invlist
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(10**9+7)

for i in range(h-a):
    cnt+=(combi(b+i-1,i)*combi(w+h-2-b-i,h-1-i))%(10**9+7)
print(cnt)

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce

MOD = (10 ** 9) + 7

factors = [1, 1]
finv = [1, 1]
inv = [0, 1]

for i in range(2, 200010):
    factors.append(factors[i - 1] * i % MOD)
    inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)
    finv.append(finv[i - 1] * inv[i] % MOD)

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

def ncr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

assert ncr(3, 4) == 0

def g(h, w, a, b):
    prev = [1] * w
    cur = [0] * w

    for i in range(h - 1):
        cur[0] = 1
        start = 0
        if i >= h - 1 - a:
            cur[b] = prev[b]
            start = b
        for j in range(start + 1, w):
            cur[j] = cur[j - 1] + prev[j]
            cur[j] = cur[j] % (1e9 + 7)
        prev, cur = cur, prev
    return prev[-1]

def f(H, W, A, B):
    count = 0
    x, y, a = H - A - 1, W + A - 2, A - 1
    for i in range(B, W): # bottom-left to top-right
        c1 = nck(x + i, i)
        c2 = nck(y - i, a)
        c = c1 * c2
        count += c
        count = count % MOD
    print(count)
    return int(count)

## assert f(4, 4, 0, 0) == 20
# assert f(4, 4, 2, 2) == 10
#assert f(2, 3, 1, 1) == 2
#assert f(10, 7, 3, 4) == 3570
#assert f(100000, 100000, 99999, 99999) == 1
#assert f(100000, 100000, 44444, 55555) == 738162020

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

Submission status: Wrong Answer

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod
 
 
mod = 10**9+7 #出力の制限
N = 200000
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())

x = cmb(W+H-B-2,H-1,mod)
ans = x
#print(x)

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

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
factorials = [1]
for i in range(1, 200000):
    factorials.append((factorials[-1] * i) % MOD)


def combinations(n, k):
    return (factorials[n] / (factorials[k] * factorials[n - k])) % MOD


def f(x, y):
    return combinations(x + y - 2, x - 1)


h, w, a, b = map(int, input().split())
res = 0
for y in range(1, h - a + 1):
    res += (f(b, y) * f(w - b, h - y + 1)) % MOD

print(int(res))

Submission status: Wrong Answer

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

h1=h-a
h2=h
w1=b
w2=w-b

ans=0
for i in range(h1):
    a=math.factorial(i+w1-1)%mod
    b=math.factorial(i)%mod
    c=math.factorial(w1-1)%mod
    d=math.factorial(h-i-1+w2-1)%mod
    e=math.factorial(h-i-1)%mod
    f=math.factorial(w2-1)%mod
    ans+=((a//(b*c))*(d//(e*f)))%mod
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    h,w,a,b=map(int,input().split(' '))
    mod = 10**9+7
    mx=max(h,w)
    fac=[1]*(h+w+1)
    for i in range(1,h+w+1):
        fac[i]=fac[i-1]*i%mod
    rev=[1]*(mx+1)
    rev[-1]=pow(fac[mx],mod-2,mod)
    for i in range(mx-1,-1,-1):
        rev[i+1]=rev[i+1]*(i+1)%mod
    const=rev[h-a-1]*rev[a-1]%mod
    ans = sum(fac[h - a + i - 1] * rev[i] * fac[a + w - 2 - i] * rev[w - i - 1] % mod for i in range(b, w))
    print(ans * const % mod)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W,A,B = map(int,input().split())
MOD = 10**9 + 7
FAC = [1]
INV = [1]
for i in range(1,H+W+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))
#print(FAC)
#print(INV)

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
H,W,A,B=map(int,input().split())

def tansaku(x,y):#これずっと使ったら時間足りなくなりそう
    ans=1
    upper=(x+y)
    under=min(x,y)
    for i in range(under):
        ans*=(upper-i)/(under-i)
    return ans
    

l_block=1
r_block=tansaku(H-1,W-B-1)
ans=l_block*r_block

for i in range(1,H-A):
    l_block*=(B+i)/i
    r_block*=(H-i)/(H+W-B-i-1)
    ans+=(l_block-l_block*i/(B+i))*r_block

print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                prime[i*j]=False
                j+=1
        i+=1
    return(r)

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

    ans = [0]*(W-B)

    ans[0] = 1

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

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

    return(sum(ans)%mod)


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

Submission status: Wrong Answer

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

#階乗を求める
fact_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    fact_l[i] *= (fact_l[i-1]*i)%mod

#逆元
factinv_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    factinv_l[i] = pow(fact_l[i],mod-2,mod)
    
#必ず通るポイントまでの組み合わせ
point1 = [1 for i in range(w-b)]
for i in  range(len(point1)):
    yoko = b+i 
    tate = h-a-1
    n = yoko+tate
    r = yoko
    point1[i] = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod

#point1からの経路
out = 0
for i in range(len(point1)):
    yoko = w-b-i-1
    tate = a-1
    n = yoko+tate
    r = yoko
    case = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod
    out += point1[i]*case%mod
print(out)

Submission status: Wrong Answer

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

H, W, A, B = map(int, input().split())
mod = 10**9 + 7
ans = 0
for i in range(1,H-A+1):
  if i == 1:
    if W-B == 1:
      ans += 1
    else:
      ans += combinations_count(W-B+H-2,W-B-1) % mod
  else:
    X = combinations_count(i+B-2,i-1) % mod
    Y = combinations_count(W-B+H-i-1,W-B-1) % mod
    ans += (X*Y) % mod
print(ans)

Submission status: Wrong Answer

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

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(a,h):
  for j in range(b,w):
    l[i][j]=l[i-1][j]+l[i][j-1]

print(l)

Submission status: Wrong Answer

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

def inv(x, p):
    pp = p-2
    ans = 1
    while pp > 0:
        if pp % 2 == 1:
            ans = (ans * x) % p
        x = (x ** 2) % p
        pp //= 2
    return ans

I = [1] + [inv(i, mod) for i in range(1, h+w+1)]

a0 = 1
a1 = 1
for i in range(w-b+a-1, w-b-1, -1):
    a1 = (a1 * i) % mod
# print(a1)
for i in range(a+1):
    #print("i",i)
    a1 = (a1 * I[i]) % mod

A0 = [a0]
A1 = [a1]
for i in range(1, h-a):
    a0 = (a0 * (b-1+i)) % mod
    a0 = (a0 * I[i]) % mod
    A0.append(a0)

    a1 = (a1 * (w-b+a-1+i)) % mod
    a1 = (a1 * I[w-b+i]) % mod
    A1.append(a1)

# print(A0)
# print(A1)
ans = 0
for i in range(h-a):
    pl = (A0[i] * A1[-i-1]) % mod
    ans = (ans + pl) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

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

fact = [1]

# 累積乗を作る
for i in range(1, h+w-1):
    fact.append(fact[-1] * i % MOD)

# 累積乗の逆元
inv_fact = [pow(fact[-1], MOD-2, MOD)] # x^(-1) = x^(10^9+5) % (10^9+7), フェルマーの小定理
for i in range(h+w-2, 0, -1): # xが最大の場合を求め、後ろ向きに計算していく
    inv_fact.append(inv_fact[-1] * i % MOD)
inv = list(reversed(inv_fact)) # 逆順に取得

#print(fact, inv_fact, inv)
def comb(a, b):
    return (fact[a] * inv[b] * inv[a-b])

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

print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

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

ans = 0
for x in range(b, w):
    t = (factorial(x+h-1-a) // (factorial(x) * factorial(h-1-a))) % MOD
    ans += (t * (factorial((a-1+w-x-1)) // (factorial(w-x-1) * factorial(a-1))) % MOD)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
H,W,A,B=map(int,input().split())
# H,W,A,B=10,7,3,4
# H,W,A,B=4,4,2,2
array=[[0 for i in range(W)] for j in range(H)]

#S->P->G の実装
#与えられたHとWで最大値を算出
# ue=math.factorial( H-1 + W-1 )
# sita=math.factorial( H-1 )*math.factorial( W-1 )
# result = ue//sita
# print(result)
# print("---------------")
ans=[]
#S->PとP->Gの実装
for i in range(0,H-A):
    ue=math.factorial( H-i-1 + W-B-1 )
    sita=math.factorial( H-i-1 )*math.factorial( W-B-1 )
    result1 = ue//sita

    ue=math.factorial( i + B-1)
    sita=math.factorial(i)*math.factorial(B-1)
    result2 = ue // sita
    # print("S->P",result1)
    # print("P->G",result2)
    # print("S->P->G",result1*result2)
    ans.append(result1*result2)

# ue=math.factorial( H-A-1 + W-B-1 )
# sita=math.factorial( H-A-1 )*math.factorial( W-B-1 )
# result = ue//sita
# print("S->P",result)

# ue=math.factorial( A + B-1)
# sita=math.factorial(A)*math.factorial(B-1)
# result = ue // sita
# print("P->G",result)

print(sum(ans))
# print(*array,sep="\n")
# print(array[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,A,B=map(int,input().split())
# H,W,A,B=2,3,1,1
# H,W,A,B=10,7,3,4
array=[[0 for i in range(W)] for j in range(H)]

#進めないところ塗りつぶし+1埋め
for i in range(H):
    for j in range(W):
        if i==0 or j==0:
            array[i][j]=1
        if H-A<=i and j<B:
            array[i][j]=-1
# array[3][6]=5

def search(k,m):
    
    #スタート地点
    if k==0 and m==0:
        pass
    #縦0横Ｍ
    elif k==0:
        array[k][m]=array[k][m-1]
    #縦K横0
    elif m==0:
        array[k][m]=array[k-1][m]
    #-1を含む計算
    elif k-1 == -1:
        array[k][m]=array[k][m-1]
    elif m-1 == -1:
        array[k][m]=array[k-1][m]
    else:
        array[k][m]=array[k-1][m]+array[k][m-1]
    
    #Kが閾値を超えていないで
    if k+1<H :
        #-1出もなくて、上下に値がある場合
        if array[k+1][m]!=-1 :
            search(k+1,m)
    if m+1<W :
        if array[k][m+1]!=-1 :
            search(k,m+1)

#升目の計算
QUE=deque()
array[0][0]=1

# search(0,0)

for i in range (0,H):
    for j in range(0,W):

        if (0<i and 0<j) and array[i][j]!=-1 :
            if array[i-1][j]>=1 and array[i][j-1]>=1:
                array[i][j] = array[i-1][j]+array[i][j-1]
            elif array[i-1][j]==-1 :
                array[i][j] = array[i][j]+array[i][j-1]
            elif array[i][j-1]==-1 :
                array[i][j] = array[i-1][j]+array[i][j]
        
        # #iが閾値を超えていないで
        # if i+1<H :
        #     #-1出もなくて、上下に値がある場合
        #     if array[i+1][j]!=-1 :
        #         search(i+1,j)
        # if j+1<W :
        #     if array[i][j+1]!=-1 :
        #         search(i,j+1)
    
# print(*array,sep="\n")
print(array[H-1][W-1])

Submission status: Wrong Answer

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

grid=[[0]*(w+1) for _ in range(h+1)]
grid[1][1]=1

for x in range(1,w+1):
  for y in range(1,h+1):
    if x>b or y<h-a+1:
      grid[y][x]=grid[y][x]+grid[y-1][x]+grid[y][x-1]
    
print(grid[y][x])

Submission status: Wrong Answer

Solution code:
H,W,A,B=map(int,input().split())
m=[[0 for _ in range(W)] for _ in range(H)]
m[0][0]=1

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

Submission status: Wrong Answer

Solution code:
def debug(l):
    for i in l:
        print(i)



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

#メモ
dp=[[0 for i in range(w)]for j in range(h)]
#行けない場所は-1
for i in range(h-a,h):
    for j in range(b):
        dp[i][j]=-1
#1パターンしかないところを埋めていく
for i in range(a):
    dp[i][0] = 1
for i in range(w):
    dp[0][i] = 1  
    
#debug(dp)
    
#巡回する
for i in range(w):
    for j in range(h):
        #0(行けるマス)だった場合
        if dp[j][i]==0:
            #片側が行けないマスだった場合
            if dp[j][i-1] == -1:
                dp[j][i] = dp[j-1][i]
            else:
                dp[j][i] = dp[j-1][i]+dp[j][i-1]
#debug(dp)

print(dp[h-1][w-1]%(10**9+7))

Submission status: Wrong Answer

Solution code:
CONST=10**9+7
H,W,A,B=map(int,input().split())
def kaizyo(num):
    multi=1
    for i in range(1,num+1):
        multi*=i
    return multi

sum=0
for i in range(0,W-B):
    sum+=(kaizyo(H-A-1+B+i)%CONST/(kaizyo(H-A-1)*kaizyo(B+i)%CONST)%CONST)*(kaizyo(A-1+W-B-1-i)%CONST/(kaizyo(A-1)*kaizyo(W-B-1-i)%CONST)%CONST)

print(int(sum%CONST))

Submission status: Wrong Answer

Solution code:
H,W,A,B = map(int,input().split())
MOD = 10**9+7
L = [1]
for i in range(B,B+H-A-1):
    L.append((L[-1]*i//(i-B+1))%MOD)
R = [1]
for i in range(W-B,W-B+H-1):
    R.append((R[-1]*i//(i-W+B+1))%MOD)
ans = 0
for i in range(len(L)):
    ans += (L[i]*R[-i-1])%MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
H, W, A, B = map(int, input().split())
T = [[-1 for i in range(W)] for j in range(H)]

# 初期値　2次元テーブルを作成
T[0][1:] = [1 for k in range(W)]
for j in range(H):
	T[j][0] = 1 if j>0 else 0

# 下からA個,左からB個の枠に対して0による塗りつぶし
for j in range(A):
	T[H-1-j][:B] = [0 for k in range(B)]

# 一つ左の升目と一つ上の升目を足し合わせて各升目に行く方法が何通りかを出力
for j in range(1,H):
	for i in range(1,W):
		if T[j][i] != 0:
			T[j][i] = T[j-1][i] + T[j][i-1]

print(T[H-1][W-1]%(10**9-7))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
H, W, A, B = map(int, input().split())
T = [[-1 for i in range(W)] for j in range(H)]
S = 0 
# 初期値　2次元テーブルを作成
for i in range(W-1):
	T[0][i+1] = 1
for j in range(H-1):
	T[j+1][0] = 1
T[0][0]=0

# 下からA個,左からB個の枠に対して0による塗りつぶし
for j in range(A):
	for i in range(B):
		T[H-1-j][i] = 0

# 一つ左の升目と一つ上の升目を足し合わせて各升目に行く方法が何通りかを出力
for j in range(1,H):
	for i in range(1,W):
		if T[j][i] != 0:
			T[j][i] = T[j-1][i] + T[j][i-1]

print(T[H-1][W-1]%(10**9-7))

Submission status: Wrong Answer

Solution code:
high, width, y, x = map(int, input().split())

def nCr(n, r):
    return (((fact[n]*finv[n-r]%mod)*finv[r])%mod)

mod = 10**9 + 7
inv = mod - 2
maxn = high + width - 2
fact = [0] * (maxn+1)
finv = [0] * (maxn+1)
fact[0] = fact[1] = 1
finv[0] = finv[1] = 1

# 階乗を求める
for i in range(2, maxn+1):
    fact[i] = (fact[i-1] * i) % mod

# 階乗の逆元を求める
for i in range(2, maxn+1):
    finv[i] = pow(fact[i], inv, mod)

route = 0

for i in range(1, high-y+1):
        route = (route + (nCr(x+i-2, i-1) * nCr(width+high-x-1-i, high-i)) % mod)
print(int(route))