Problem:


Score : 400 points

Problem Statement

We have a large square grid with H rows and W columns.
Iroha is now standing in the top-left cell.
She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.

However, she cannot enter the cells in the intersection of the bottom A rows and the leftmost B columns. (That is, there are A×B forbidden cells.) There is no restriction on entering the other cells.

Find the number of ways she can travel to the bottom-right cell.

Since this number can be extremely large, print the number modulo 10^9+7.

Constraints

 1 ≦ H, W ≦ 100,000

 1 ≦ A < H

 1 ≦ B < W

Input

The input is given from Standard Input in the following format:

H W A B

Output

Print the number of ways she can travel to the bottom-right cell, modulo 10^9+7.

Sample Input 1

2 3 1 1

Sample Output 1

2

We have a 2×3 grid, but entering the bottom-left cell is forbidden. The number of ways to travel is two: "Right, Right, Down" and "Right, Down, Right".

Sample Input 2

10 7 3 4

Sample Output 2

3570

There are 12 forbidden cells.

Sample Input 3

100000 100000 99999 99999

Sample Output 3

1

Sample Input 4

100000 100000 44444 55555

Sample Output 4

738162020



Sample input:
2 3 1 1


Sample output:
2

Submission status: Accepted

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

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

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

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

    

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

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

print su

Submission status: Accepted

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

class Combin(object):
    def __init__(self, max_n, mod = 10**9 + 7):
        self.max_n = max_n
        self.mod = mod
        self.fac = self._init_factorials()
        self.inv = self._init_inv()
        
    def _init_factorials(self):
        N = self.max_n
        mod = self.mod
        f = 1
        fac = [1] * (N + 1)
        for i in range(1, N + 1):
            f *= i
            f %= mod
            fac[i] = f
        return fac

    def _init_inv(self):
        N = self.max_n
        mod = self.mod
        ret = pow(self.fac[N], mod - 2, mod)
        inv = [1] * (N + 1)
        inv[N] = ret
        for i in range(N-1, 0, -1):
            ret *= i + 1
            ret %= mod
            inv[i] = ret
        return inv

    def nCb(self, n, b):
        return (self.fac[n] * self.inv[b] * self.inv[n-b]) % self.mod


def solve(H, W, A, B):
    mod = 10 ** 9 + 7
    cb = Combin(H + W)
    ans = cb.nCb(H + W - 2, H - 1)
    t1 = B + H - 1
    t2 = B - 1
    t3 = W - B - 2
    t4 = W - B - 1
    for a in range(1, A + 1):
        d = cb.nCb(t1 - a, t2) * cb.nCb(t3 + a, t4)
        ans -= d
        ans %= mod
    return ans

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

Submission status: Accepted

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

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

factinv = [1] * (h + w - 2)
factinv[h + w - 3] = pow(fact[h + w - 3], C - 2, C)
for x in reversed(range(2, h + w - 3)):
    factinv[x] = (factinv[x + 1] * (x + 1)) % C

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

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

print(ans)

Submission status: Accepted

Solution code:
M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*pow(I+1,M-2,M)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*pow(I*(W+H-B-1-I),M-2,M)%M;Z+=C
print(Z%M)

Submission status: Accepted

Solution code:
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I*(W+H-B-1-I))%M;Z+=C
print(Z%M)

Submission status: Accepted

Solution code:
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)%M*F(I*(W+H-B-1-I))%M;Z=(Z+C)%M
print(Z)

Submission status: Accepted

Solution code:
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*(H-I)*F(I*(W+H-B-1-I))%M;Z=(Z+C)%M
print(Z)

Submission status: Accepted

Solution code:
M=10**9+7;F=[pow(X,M-2,M)for X in range(2*10**5)];H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F[I+1]%M
for I in range(1,H-A):C=C*(B-1+I)*F[I]*(H-I)*F[W+H-B-1-I]%M;Z=(Z+C)%M
print(Z)

Submission status: Accepted

Solution code:
M=10**9+7;F=lambda X:pow(X,M-2,M);H,W,A,B=map(int,input().split());Z=C=1
for I in range(H-1):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

Submission status: Accepted

Solution code:
F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

Submission status: Accepted

Solution code:
def Combination_mod(n, k):
    ret = f[n]
    ret = (ret * finv[k]) % mod
    ret = (ret * finv[n - k]) % mod
    return ret

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

x = []
xi = b
xj = h - a - 1
while xi < w and xj >= 0:
    x.append([xi, xj])
    xi += 1
    xj -= 1

n = w + h
f = [0] * n
finv = [0] * n

f[0] = 1
finv[0] = finv[1] = 1
for i in range(1, n):
    f[i] = (f[i - 1] * i) % mod

finv[n - 1] = pow(f[n - 1], mod - 2, mod)
for i in range(n - 2, 1, -1):
    finv[i] = ((i + 1) * finv[i + 1]) % mod

ans = 0
for i, j in x:
    ans1 = Combination_mod(i + j, i)
    ans1 *= Combination_mod(w - 1 - i + h - 1 - j, w - 1 - i)
    ans += ans1
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n, k = LI()
d = LI()

limit = 11*n
while n < limit:
    flg = 1
    for x in list(str(n)):
        if int(x) in d:
            flg = 0
            break
    if flg:
        print(n)
        break
    n += 1

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from time import perf_counter

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

# import sys
# sys.stdout = open("e:/cp/output.txt","w")
# sys.stdin = open("e:/cp/input.txt","r")



n,k = map(int,input().split())
d= list(map(int,input().split()))
test = [1,2,3,4,5,6,7,8,9]

for item in range(k):
    if d[item]==0:
        print(n)
        exit()

result =[]
for item in test:
    if item not in d:
        result.append(item)
n= list(str(n))
# final_result =[]
for item in range(len(n)):
    if int(n[item])>0:
        if n[item] != result[item]:
            n[item] = str(result[item])
ans = "".join(n)
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from time import perf_counter

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





n,k = map(int,input().split())
d= list(map(int,input().split()))
test = [1,2,3,4,5,6,7,8,9]

for item in range(k):
    if d[item]==0:
        print(n)
        exit()

result =[]
for item in test:
    if item not in d:
        result.append(item)
n= list(str(n))
# final_result =[]
for item in range(len(n)):
    if int(n[item])>0:
        if n[item] != result[item]:
            n[item] = str(result[item])
ans = "".join(n)
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

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

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

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

comb = Combination(10**5)

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

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

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

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

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

print(total)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
from scipy.special import comb

# 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


# 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


hwab = list(map(lambda x: int(x), input().split(" ")))

h = hwab[0]
w = hwab[1]
a = hwab[2]
b = hwab[3]

mod = 10**9 + 7

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

print(int(res) % mod)

Submission status: Runtime Error

Solution code:
hwab = list(map(lambda x: int(x), input().split(" ")))

h = hwab[0]
w = hwab[1]
a = hwab[2]
b = hwab[3]

mod = 10**9 + 7

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

print(res % mod)

Submission status: Runtime Error

Solution code:
def main():
    import math
    h,w,a,b=map(int,input().split())
    h-=1
    w-=1
    a-=1
    b-=1
    N=math.factorial(w-b-1+h)/math.factorial(h)/math.factorial(w-b-1)
    h1=h-1
    while h1>a:
        z=h-h1+b
        z1=w-b-1+h1
        N+=math.factorial(z)/math.factorial(h-h1)/math.factorial(b)*math.factorial(z1)/math.factorial(w-b-1)/math.factorial(h1)
        h1-=1
    
    print(int(N%(10**9+7)))
  
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
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
    inv[0]=1
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
    elif w==b+1:
        x=(fac[b-1+i]*inv[b-1]*inv[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: Runtime Error

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n+r) // (math.factorial(n) * math.factorial(r))

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

ans = 0

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

print(int(ans%(1e+9 + 7)))

Submission status: Runtime Error

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

def factor(n,k):
    assert n>=k
    if n == k:
        return 1
    else:
        return n*factor(n-1,k)

def comb(n,k):
    if k < n/2:
        return int(factor(n,n-k) / factor(k,0))
    else:
        return int(factor(n,k) / factor(n-k,0))

result = 0
for i in range(min(H-A, W-B)+1):
    f1 = comb(B+H-A, B+i) % N
    f2 = comb(W-B+A, A+i) % N
    result += f1 * f2
print(result % N)

Submission status: Runtime Error

Solution code:
def irohamasu(i, j, H, W, A, B):
    if (i >= H - A) and (j <= B - 1):
        return 0
    elif i == 0 & j == 0:
        return 1
    elif i == 0:
        return irohamasu(i, j-1, H, W, A, B)
    elif j == 0:
        return irohamasu(i-1, j, H, W, A, B)
    else:
        return (irohamasu(i-1, j, H, W, A, B) + irohamasu(i, j-1, H, W, A, B))
                
H, W, A, B = map(int, input().split())
                
answer = irohamasu(H-1, W-1, H, W, A, B)
print(answer % (10**9 + 7))

Submission status: Runtime Error

Solution code:

import math

def re_factorial(n, r):
    if n <= r:
        return 1
    return n * re_factorial(n-1,r)

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

ans = 0

for dx in range(B+1,W+1):
    x = W - dx
    if y >= dx-1:
        xn = re_factorial(dx-1,1)
        nn = re_factorial(dx-1+y, y)
        Ansn = nn / xn
        if x >= A-1:
            ym = re_factorial(A-1,1)
            mm = re_factorial(x+A-1,x)
            Ansm = mm / ym
        else:
            xm = re_factorial(x,1)
            mm = re_factorial(x+A-1,A-1)
            Ansm = mm / xm
    else:
        yn = re_factorial(y,1)
        nn = re_factorial(dx-1+y, dx-1)
        Ansn = nn / yn
        if x >= A-1:
            ym = re_factorial(A-1,1)
            mm = re_factorial(x+A-1,x)
            Ansm = mm / ym
        else:
            xm = re_factorial(x,1)
            mm = re_factorial(x+A-1,A-1)
            Ansm = mm / xm
    ans += Ansn * Ansm

ans = int(ans)%1000000007
print(int(ans))

Submission status: Runtime Error

Solution code:
import math


H, W, A, B = map(int, input().split())
y = H - A -1
ans = 0

for x in range(B,W):
    yn = math.factorial(y)
    xn = math.factorial(x)
    nn = math.factorial(y+x)
    Ansn = nn / (xn * yn)
    xm = math.factorial(W-x-1)
    ym = math.factorial(A-1)
    mm = math.factorial(W-x-1+A-1)
    Ansm = mm / (xm * ym)
    ans += Ansn * Ansm

ans = ans%1000000007
print(int(ans))

Submission status: Runtime Error

Solution code:
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
size = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

ans = 0

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

print(ans)

Submission status: Runtime Error

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

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/2)**2 * x % mod

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

def combi(n, m):
    return factorial[n] * inverseFactorial[m] * inverseFactorial[n-m] % mod

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

Submission status: Runtime Error

Solution code:
import math
h,w,a,b = map(int, input().split())
result = 0
for i in range(b,w):
    result += ((math.factorial((i)+(h-a-1))) / (math.factorial(i) * math.factorial(h-a-1))) * ((math.factorial((w-i-1)+(a-1))) / (math.factorial(w-i-1)*math.factorial(a-1)))
result = int(result%(10**9 + 7))
print(result)

Submission status: Runtime Error

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

f = [1 for _ in range(n)]
for i in range(1, n):
    f[i] = f[i-1] * i

def f_inv(x):
    return pow(f[x], mod-2, mod)

def comb(n, k):
    return (f[n] * f_inv[k] % mod) * f_inv[n-k] % mod

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

print(ans)

Submission status: Runtime Error

Solution code:
#Iroha and a grid
#abc 042

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


def dp(x,y,h,w,a,b):
    if x==-2:
        c=1
      
        
    else:
        if x==w-1 and y==h-1:
            return 1
        if x>=w or y>=h or (x<b and y>=h-a):
            return 0
        ans=dp(x+1,y,h,w,a,b)+dp(x,y+1,h,w,a,b)
        return ans

print(dp(0,0,h,w,a,b)%mod)

Submission status: Runtime Error

Solution code:
#Iroha and a grid
#abc 042

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


def dp(x,y,h,w,a,b):
  	if x==-2:
      	c=1
      
        
    else:
        if x==w-1 and y==h-1:
            return 1
        if x>=w or y>=h or (x<b and y>=h-a):
            return 0
        ans=dp(x+1,y,h,w,a,b)+dp(x,y+1,h,w,a,b)
        return ans

print(dp(0,0,h,w,a,b)%mod)

Submission status: Runtime Error

Solution code:
#Iroha and a grid
#abc 042

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

def dp(x,y,h,w,a,b):
    if (x,y) in memo:
        return memo[(x,y)]
    else:
        if x==w-1 and y==h-1:
            return 1
        if x>=w or y>=h or (x<b and y>=h-a):
            return 0
        ans=dp(x+1,y,h,w,a,b)+dp(x,y+1,h,w,a,b)
        memo[(x,y)]=ans
    return memo[(x,y)]
ans=dp(0,0,h,w,a,b)%mod
print(ans)

Submission status: Runtime Error

Solution code:
#Iroha and a grid
#abc 042

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

def dp(x,y,h,w,a,b):
    if (x,y) in memo:
        return memo[(x,y)]
    else:
        if x==w-1 and y==h-1:
            return 1
        if x>=w or y>=h or (x<b and y>=h-a):
            return 0
        ans=dp(x+1,y,h,w,a,b)+dp(x,y+1,h,w,a,b)
        memo[(x,y)]=ans
    return memo[(x,y)]

print(dp(0,0,h,w,a,b)%mod)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().rstrip().split())
dislikes = list(map(int,input().rstrip().split()))
n = str(n)
len_n = len(n)
separate_n = [int(s) for s in n]

pay = separate_n.copy()
up_nextlevel = False
for i in range(len(separate_n)-1,-1,-1):
    up_nextlevel = False
    if separate_n[i] in dislikes:
        for j in range(10):
            num = separate_n[i]+j
            if num > 9:
                num -= 10
                up_nextlevel = True
            if not(num in dislikes):
                pay[i] = num
                break
    else:
        continue
if up_nextlevel:
    for i in range(1,10):
        if not(i in dislikes):
            print(i,end="")
            break
for p in pay:
    print(p,end="")

Submission status: Runtime Error

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

sg = 0

i = 0 #場合分け
svi = factorial(i+b)/factorial(i)/factorial(b)
vig = factorial(h-i-1+w-b-1)/factorial(h-i-1)/factorial(w-b-1)
sg = sg + svi*vig

# 1<= i <= h-a の時
for i in range(1,h-a):
    svj = svi = factorial(i-1+b)/factorial(i-1)/factorial(b)
    svi = factorial(i+b)/factorial(i)/factorial(b)
    vig = factorial(h-i-1+w-b-1)/factorial(h-i-1)/factorial(w-b-1)
    sg = sg + (svi-svj)*vig

print(int(sg%(10**9+7)))

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, radians, 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


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: Runtime Error

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, 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


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: Runtime Error

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, 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


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: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, 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


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: Runtime Error

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: Runtime Error

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


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: Runtime Error

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, gcd
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 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

lim = 2*10**6
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: Runtime Error

Solution code:
def func(i, j, h, w, a, b):
    if j == 0:
        return 1
    elif i == 0:
        if j < h - a:
            return 1
        else:
            return 0
    else:
        if 0 < i < b and h - a <= j < h:
            return 0
        else:
            return func(i-1, j, h, w, a, b) + func(i, j-1, h, w, a, b)


h, w, a, b = (int(x) for x in input().split())
y = func(w-1, h-1, h, w, a, b)
y = y % (1000000007)
print(y)