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

Solution code:
nums = input().split()
H = int(nums[0])
W = int(nums[1])
A = int(nums[2])
B = int(nums[3])

from math import factorial

#全体
total = factorial(H + W -2) / factorial(W-1) / factorial(H - 1)

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

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

print(total - forbidden)

Submission status: Runtime Error

Solution code:
import math

HWAB=input().split()
H=int(HWAB[0])
W=int(HWAB[1])
A=int(HWAB[2])
B=int(HWAB[3])

temp1=0
temp2=0
goukei=0
for i in range(H-A):
    temp1=int(math.factorial(i+B-1)/math.factorial(i)/math.factorial(B-1))
    temp2=int(math.factorial(W-B-1+H-i-1)/math.factorial(W-B-1)/math.factorial(H-i-1))
    goukei+=temp1*temp2
    goukei=goukei%1000000007
print(goukei)

Submission status: Runtime Error

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

    # 予め階乗を計算しておく
    f = [1]
    for i in range(H+W-B):
        f.append(f[i]*(i+1)%mod)

    # 組み合わせ関数
    def comb_mod(n, r, p):
        return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

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

    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    # 予め階乗を計算しておく
    f = [1]
    for i in range(H+W-B):
        f.append(f[i]*(i+1)%mod)

    # 組み合わせ関数
    def comb_mod(n, r, p):
        return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=200000
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
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+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)

Submission status: Runtime Error

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-i)*(w-b+1+i),w-b+1+i)*comb((w-b-i)*(a+1+i),a+1+i)
print(t%mod)

Submission status: Runtime Error

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

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

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

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

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

Submission status: Runtime Error

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

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

prev_com1 = 0
ans = 0
for i in range(h-a):
  com1 = cmb(i+b,b)
  com2 = cmb(h-b+h, h)
  ans += (com1 - prev_com1)*com2
  prev_com1 = com1
print(ans)

Submission status: Runtime Error

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

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

h-a
prev_com1 = 0
ans = 0
for i in range(h-a):
  com1 = cmb(i+b,b)
  com2 = cmb(h-b+h, h)
  ans += (com1 - prev_com1)*com2
print(ans)

Submission status: Runtime Error

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,H-A):
    P = f(i,B+1)
    Q = f(H-i+1,W-B)
    T = T + P*Q
print(T)

Submission status: Runtime Error

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

#マス目と通れないマスの入力
h,w,a,b = map(int,input().split())

ha = h-a
total = 0
for i in range(ha):
  right = b-1
  down = i
  first = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  right = w-b-1
  down = h-i-1
  last = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  total = total + int(first * last)

warizan = int(total%1000000007)
print(warizan)

Submission status: Runtime Error

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

#マス目と通れないマスの入力
h,w,a,b = map(int,input().split())

ha = h-a
total = 0
for i in range(ha):
  right = b-1
  down = i
  first = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  right = w-b-1
  down = h-i-1
  last = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  total = total + int(first * last)

print(int(total%1000000007))

Submission status: Runtime Error

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

#マス目と通れないマスの入力
h,w,a,b = map(int,input().split())

ha = h-a
total = 0
for i in range(ha):
  right = b-1
  down = i
  first = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  right = w-b-1
  down = h-i-1
  print("right:"+str(right)+"down:"+str(down))
  last = math.factorial(right+down) / (math.factorial(right)*math.factorial(down))
  print("first:"+str(first)+"last:"+str(last))
  total = total + int(first * last)
  print("total:"+str(total))

print(int(total%1000000007))

Submission status: Runtime Error

Solution code:
height, width, disabledHeight, disabledWidth = map(int, input().split())
def getPattern(x, y):
  if (x <= disabledWidth) and (y > height - disabledHeight):
    return 0
  if (x == 1) or (y == 1):
    return 1
  return getPattern(x-1, y) + getPattern(x, y-1)
print(getPattern(width, height) % (pow(10, 9) + 7))

Submission status: Runtime Error

Solution code:
height, width, disabledHeight, disabledWidth = map(int, input().split())
def getPattern(x, y):
  if (x <= disabledWidth) and (y > height - disabledHeight):
    return 0
  if (x == 1) or (y == 1):
    return 1
  return getPattern(x-1, y) + getPattern(x, y-1)
print(getPattern(width, height))

Submission status: Runtime Error

Solution code:
height, width, disabledHeight, disabledWidth = map(int, input().spilit())
def getPattern(x, y):
  if (x == 1) or (y == 1):
    return 1
  if (x <= disabledWidth) or (y > height - disabledHeight):
    return 0
  return getPattern(x-1, y) + getPattern(x, y-1)
print(getPattern(width, height))

Submission status: Runtime Error

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

stairs = [1]
for i in range(1, h+w+1):
    stairs.append(stairs[i-1]*i%mod)

inverse_stairs = [0]*(h+w)
inverse_stairs[h+w-1] = modpow(stairs[h+w-1], mod-2)
for i in range(h+w-2, -1, -1):
    inverse_stairs[i] = inverse_stairs[i+1] * (i+1) % mod
    
def modpow(x, y):   
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return modpow(x, y//2)**2 % mod
    else            : return modpow(x, y//2)**2 * x % mod

ret = 0

for i in range(w-b):
    com = stairs[w-i+h-a-2]%mod
    com = com*inverse_stairs[w-i-1]%mod
    com = com*inverse_stairs[h-a-1]%mod
    com = com*stairs[i+a-1]%mod
    com = com*inverse_stairs[i]%mod
    com = com*inverse_stairs[a-1]%mod
    ret += com

print(ret%mod)

Submission status: Runtime Error

Solution code:
import fractions
import math

MOD = math.pow(10, 9) + 7


def calc_routes(dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return int(fractions.Fraction(
            math.factorial(dx + dy),
            math.factorial(dx) * math.factorial(dy)
        ))


def check(h, w, a, b):
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(*d1)
        r2 = calc_routes(*d2)
        routes = r1 * r2
        all_routes += routes
        p = (p[0] + 1, p[1] - 1)
    return int(all_routes % MOD)


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // (math.factorial(a) * math.factorial(b))
    p2end = math.factorial(c + b) // (math.factorial(c) * math.factorial(d))
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // (math.factorial(a) * math.factorial(b))
    p2end = math.factorial(c + b) // (math.factorial(c) * math.factorial(d))
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input.split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
    p2end = math.factorial(c + b) // math.factorial(c) // math.factorial(d)
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input.split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // (math.factorial(a) // math.factorial(b))
    p2end = math.factorial(c + b) // (math.factorial(c) // math.factorial(d))
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input.split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import gamma
cnt=0
h,w,a,b=map(int,input().split())
for k in range(0,h-a):
    cnt+= (int((gamma(b+k)*gamma(h+w-k-b-1))/(gamma(k+1)*gamma(b)*gamma(w-b)*gamma(h-k))))//(10^9+7)
print(cnt)

Submission status: Runtime Error

Solution code:
class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)

    def dequeue(self):
        return self.data.pop(0)

    def is_Empty(self):
        if len(self.data) == 0:
            return True
        else:
            return False


mod = 1000000007
H, W, A, B = map(int, input().split())  # 縦H, 横W, 下からA左からBは入れない

counter = [[0]*W for _ in range(H)]
flag = [[False]*W for _ in range(H)]

counter[0][0] = 1

q = Queue()
q.enqueue((0, 0))

adjacents = [(0, 1), (1, 0)]
while not q.is_Empty():
    cy, cx = q.dequeue()
    for dy, dx in adjacents:
        if cy+dy >= H or cy+dy < 0 or cx+dx >= W or cx+dx < 0 or (cy+dy >= (H-A) and B > cx+dx):
            continue
        counter[cy+dy][cx+dx] += counter[cy][cx]
        if not flag[cy+dy][cx+dx]:
            q.enqueue((cy+dy, cx+dx))
            flag[cy+dy][cx+dx] = True
    if counter[1][2] == 5:
        print(counter)
        exit()


print(counter[-1][-1] % mod)
# print(counter)

Submission status: Runtime Error

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

nfact_l = [1 for i in range(h+w+1)]
def nfact_mod(n0,mod0):
    for i in range(1,len(nfact_l)):
        nfact_l[i] *= (nfact_l[i-1]*i)%mod
nfact_mod(h+w+1,mod)

#二分累乗法 あとで使う
def powfunc_mod(n0,r0,mod0):
    ans0 = 1
    r0 = bin(r0)[:1:-1]
    for i in r0:
        if i == "1":
            ans0 *= (n0 % mod0)
        n0 *= (n0 % mod0)
        ans0 %= mod0
    return ans0

nfact_inv_l = [1 for i in range(h+w+1)]
for i in range(len(nfact_inv_l)):
    nfact_inv_l[i] = powfunc_mod(nfact_l[i],mod-2,mod)

point1 = [0 for i in range(w-b)]
for i in range(len(point1)):
    #  ... = n!*r!^(p-2)*(n-r)!^(p-2) [mod]
    yoko = b+i
    tate = h-a-1
    n = yoko+tate
    r = tate
    point1[i] = (nfact_l[n]*nfact_inv_l[r]*nfact_inv_l[n-r])%mod

#point1から目的まで行く経路数
out = 0
for i in range(len(point1)):
    yoko = w-b-1+i
    tate = a-1
    n = yoko+tate
    r = tate
    out += ((((point1[i]*nfact_l[n])%mod)*nfact_inv_l[r]%mod)*nfact_inv_l[n-r])%mod

print(out)

Submission status: Runtime Error

Solution code:
import math
H, W, A, B = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(H-A):
    first = (math.factorial(B-1+i)/(math.factorial(B-1)*math.factorial(i))) % MOD
    last = (math.factorial(W+H-B-i-2)%MOD/(math.factorial(W-B-1)*math.factorial(H-i-1))) % MOD
    ans += int(first*last)
print(ans % MOD)

Submission status: Runtime Error

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

mod = 10**9 + 7

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

def comb(A,B,mod):
    return f[A] * pow(f[B],mod-2,mod) * pow(f[a-b],mod-2,mod) % mod

res = 0

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

print(res%mod)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W, A, B = map(int, input().split())
p = int(10e9+7)

D = np.zeros((H,W), dtype=int)
D[(H-A):, :B] = -1
D[0,0] = 1
u = 0
l = 0
for i in range(H):
    for j in range(W):
        if D[i,j] == 0:
            if i == 0:
                u = 0
            else:
                u = D[i-1,j]
            if D[i,j-1] == -1:
                l = 0
            elif j == 0:
                l = 0
            else:
                l = D[i,j-1]
            D[i,j] = (u+l)%p

print(D[H-1,W-1])

Submission status: Runtime Error

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)/(kaizyo(H-A-1)*kaizyo(B+i))%CONST)*(kaizyo(A-1+W-B-1-i)/(kaizyo(A-1)*kaizyo(W-B-1-i))%CONST)

print(int(sum%CONST))

Submission status: Runtime Error

Solution code:
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)/(kaizyo(H-A-1)*kaizyo(B+i)))*(kaizyo(A-1+W-B-1-i)/(kaizyo(A-1)*kaizyo(W-B-1-i)))

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

Submission status: Runtime Error

Solution code:
import sys
import math

def input():
    return sys.stdin.readline()[:-1]
h,w,a,b=map(int,input().split())
mod=10**9+7

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

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

print(ans%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

def powmod(a, n, m):
    if n == 0:
        return 1
    elif n == 1:
        return (a % m)
    elif n%2 == 0:
        s = powmod(a, int(n/2), m)
        temp = (s * s) % m
        return temp
    else:
        s = powmod(a, int(n/2), m)
        temp = ((s * s) * a) % m
        return temp

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] = powmod(fact[i], inv, mod)

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

Submission status: Runtime Error

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

def nCr(n, r):
    return ((((fact[n]*finv[n-r])%mod)*finv[r])%mod)
def powmod(a, n, m):
    if n == 0:
        return 1
    elif n == 1:
        return a
    if n%2 == 0:
        temp = (powmod(a, n/2, m) ** 2) % m
        return temp
    else:
        temp = (((powmod(a, n/2, m) ** 2) % m) * a) % m
        return temp

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] = powmod(fact[i], inv, mod)

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

Submission status: Runtime Error

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

import math
route = 0
for i in range(1,high-y+1):
    if i != high-y:
        route += ((math.factorial(x+i-1)/(math.factorial(x)*math.factorial(i-1)))%(10**9+7))*((math.factorial(width-x-2+high-i)/(math.factorial(width-x-2)*math.factorial(high-i))))%(10**9+7)
    else:
        route += ((math.factorial(x+i-1)/(math.factorial(x)*math.factorial(i-1)))%(10**9+7))*((math.factorial(width-x-1+high-i)/(math.factorial(width-x-1)*math.factorial(high-i))))%(10**9+7)
print(int(route))

Submission status: Runtime Error

Solution code:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

ans = 0
mod_parent = 10**9 + 7
for i in range( 1, w-b ) :
  ans += ( cmb( h-a-1+i, i ) %  mod_parent ) + ( cmb( a+w-i-2, a-1 ) %  mod_parent )
print( ans )

Submission status: Runtime Error

Solution code:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

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

ans = 0
mod_parent = 10**9 + 7
for i in range( a+1 ) :
  ans += ( cmb( b+h-a, i ) %  mod_parent ) + ( cmb( h+w-b, h-i ) %  mod_parent )
print( ans )

Submission status: Runtime Error

Solution code:
h,w,a,b=[int(s) for s in input().split()]
list1=[h+w-2,h-1,w-1,a+b-2,a-1,b-1]
list2=[]
list3=[]

import math
for i in range(6):
	list2.append(int(math.factorial(list1[i])))

way1=int(list2[0]/(list2[1]*list2[2]))
way2=int(list2[3]/(list2[4]*list2[5]))
allways=way1-way2
answer=int(allways%1000000007)
print(answer)

Submission status: Runtime Error

Solution code:
h,w,a,b=[int(s) for s in input().split()]
list1=[h+w-2,h-1,w-1,a+b-2,a-1,b-1]
list2=[]
list3=[]

import math
for i in range(6):
	list2.append(math.factorial(list[i]))

way1=list2[0]/(list2[1]*list2[2])
way2=list2[3]/(list2[4]*list2[5])
allways=way1-way2
answer=int(allways%1000000007)
print(answer)

Submission status: Runtime Error

Solution code:
h,w,a,b=[int(s) for s in input().split()]
list1=[h+w-1,h,w,a+b-1,a,b]
list2=[]
list3=[]

for i in range(0,4,3):
	kaijo1=1
	kaijo2=1
	for j in range (list1[i+1],list1[i]):
		kaijo1=kaijo1*j
	for k in range(1,list1[i+2]):
		kaijo2=kaijo2*k
	list2.extend([kaijo1,kaijo2])

allways=(list2[0]/list2[1])-(list2[2]/list2[3])

"""
for i in range(6):
	kaijo=1
	for j in range(1,list1[i]):
		kaijo=kaijo*j
	list2.append(kaijo)

for i in range(0,4,3):
	ways=list2[i]/(list2[i+1]*list2[i+2])
	list3.append(ways)
	
allways=list3[0]-list3[1]
"""

answer=int(allways%1000000007)
print(answer)

Submission status: Runtime Error

Solution code:
h,w,a,b=[int(s) for s in input().split()]
list1=[h+w-1,h,w,a+b-1,a,b]
list2=[]
list3=[]
for i in range(6):
	kaijo=1
	for j in range(1,list1[i]):
		kaijo=kaijo*j
	list2.append(kaijo)

for i in range(0,4,3):
	ways=list2[i]/(list2[i+1]*list2[i+2])
	list3.append(ways)

allways=list3[0]-list3[1]
answer=int(allways%1000000007)
print(answer)

Submission status: Runtime Error

Solution code:
h,w,a,b=[int(s) for s in input().split()]
list1=[h+w-1,h,w,a+b-1,a,b]
list2=[]
list3=[]
for i in range(6):
	kaijo=1
	for j in range(1,list1[i]):
		kaijo=kaijo*j
	list2.append(kaijo)

for i in range(0,4,3):
	ways=list2[i]/(list2[i+1]*list2[i+2])
	list3.append(ways)

allways=list3[0]-list3[1]
answer=allways%1000000007
print(answer)

Submission status: Runtime Error

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

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

@author: matsui
"""

def kai(a,b):
    ans=1
    for i in range(a,b-1,-1):
        ans*=i
    
    return ans

def C(a,b):
    return kai(a,(b+1))/kai((a-b),1)

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

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

@author: matsui
"""

def kai(a,b):
    ans=1
    for i in range(a,b-1,-1):
        ans*=i
    
    return ans

def C(a,b):
    return kai(a,(b+1))/kai((a-b),1)

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=ans%(1e9+7)
print(ans)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k 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 *= int(numerator[k])

    return result

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

n1 = B - 1
r1 = B - 1
n2 = W - B - 1 + H - 1
r2 = W - B - 1
route1 = cmb(n1, r1)
route2 = cmb(n2, r2)
route = route1 * route2

for i in range(1, H - A):
    k1 = (n1 + 1) / (n1 + 1 - r1)
    k2 = (n2 - r2) / n2

    route1 *= k1
    route2 *= k2

    n1 += 1
    n2 -= 1

    route += route1 * route2
    #print(i, k1, k2)
print(int(route) % (10 ** 9 + 7))

Submission status: Runtime Error

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

	fact = [0]*size
	inverse = [0]*size
	inv_cal = [0]*size
	fact[:2] = [1, 1]
	inverse[:2] = [1, 1]
	inv_cal[:2] = [0, 1]

	for i in range(2, size):
		fact[i] = (fact[i-1]*i%DIV)
		inv_cal[i] = (-inv_cal[DIV%i]*(DIV//i))%DIV
		inverse[i] = inverse[i-1]*inv_cal[i]%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)*(C(H+W-x-y-1, W-x))%DIV
		ans += tmp
		ans %= DIV

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Runtime Error

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

	fact = [0]*(H+W-A+1)
	inverse = [0]*(H+W-A+1)
	inv_cal = [0]*(H+W-A+1)
	fact[:2] = [1, 1]
	inverse[:2] = [1, 1]
	inv_cal[:2] = [0, 1]

	for i in range(2, H+W-A+1):
		fact[i] = (fact[i-1]*i%DIV)
		inv_cal[i] = (-inv_cal[DIV%i]*(DIV//i))%DIV
		inverse[i] = inverse[i-1]*inv_cal[i]%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: Runtime Error

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

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)
n%=(10**9)+7
print(int(n))

Submission status: Runtime Error

Solution code:
X, Y, Z, K = map(int, input().split())

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


A = sorted(A, key = lambda x:-x)
B = sorted(B, key = lambda x:-x)
C = sorted(C, key = lambda x:-x)

AB = [0] * (X * Y)

index = 0
for i in range(len(A)):
    for j in range(len(B)):
        AB[index] = A[i] + B[j]
        index += 1

AB = sorted(AB, key = lambda x:-x)

ABC = [0] * min(3050, X * Y * Z)
index = 0

for i in AB:
    if index >= 3000:
        break
    for j in C:
        ABC[index] = i + j
        index += 1

ABC = sorted(ABC, key = lambda x:-x)
for i in range(0,K):
    print(ABC[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
#入力
h,w,a,b=map(int,input().split(" "))
count=0
#階乗の関数を定義
def kaizyou(a):
    ans=a
    if a==1 or a==0:
        ans=1
    else:
        for i in range(1,a):
            ans=ans*(a-i)
    return int(ans)
for i in range(1,h-a+1):
    count1=kaizyou(b-1+i-1)/(kaizyou(b-1)*kaizyou(i-1))
    count2=kaizyou(w-b-1+h-i)/(kaizyou(w-b-1)*kaizyou(h-i))
    count=count+count1*count2
count=count%(1000000000+7)
count=int(count)
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
#入力
h,w,a,b=map(int,input().split(" "))
count=0
for i in range(1,h-a+1):
    count=count+math.factorial(b-1+i-1)/(math.factorial(b-1)*math.factorial(i-1))*\
    math.factorial(w-b-1+h-i)/(math.factorial(int(w-b-1))*math.factorial(h-i))
count=count%(1000000000+7)
count=int(count)
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
#入力
h,w,a,b=map(int,input().split(" "))
count=0
for i in range(1,h-a+1):
    count=count+math.factorial(b+i-1)/(math.factorial(b)*math.factorial(i-1))*\
    math.factorial(w-b-1+h-i)/(math.factorial(w-b-1)*math.factorial(h-i))
count=count%(1000000000+7)
count=int(count)
print(count)

Submission status: Runtime Error

Solution code:
def combination(n,r):
    a,b=1,1
    if r==0:
        return 1
    
    if n-r<int(n/2):
        r=n-r

    for i in range(r):
        a*=n-i
        b*=i+1

    return int(a/b)

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

    P=0
    for i in range(H-A):
        if i==H-A-1:
            P+=combination(B+i,i)*combination(W-B+H-i-2,W-B-1)
        else:
            P+=combination(B+i,i)*(combination(W-B+H-i-2,W-B-1)-\
                                   combination(W-B+H-i-3,W-B-1))

    mod=P % (10**9+7)

    print(mod)

Submission status: Runtime Error

Solution code:
S = input() #"3 2"
W, H = map(int, S.split())
STAGE = [["*" for x in range(W)] for y in range(H)]

def set_v(p, v):
	STAGE[p[1]][p[0]] = v

def get_v(p):
	return STAGE[p[1]][p[0]]

def print_stage():
	for x in STAGE:
		print(*x, sep="")

def search(cp, c):
	cx, cy = cp
	for np in ((cx+1, cy), (cx, cy+1)):
		nx, ny = np
		if W<=nx or H<=ny:
			continue
		if get_v(np) == "E":
			return c + 1
		c = search(np, c)
	return c

S = (0, 0)
E = (W-1, H-1)

set_v(S, "S")
set_v(E, "E")

c = 0
c = search(S, c)

print(c)

Submission status: Runtime Error

Solution code:
import numpy as np
H,W,A,B=map(int,input().split())
memo=np.ones((H,W),int)
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][j]=(memo[i-1][j]+memo[i][j-1])%(10**9+7)
print(memo[H-1][W-1])

Submission status: Runtime Error

Solution code:
H,W,A,B=map(int,input().split())
def kaijo(a):
    x=1
    for i in range(a):
       x=x*(i+1)
    return x
def con(a,b):
    x=kaijo(a)
    y=kaijo(b)
    z=kaijo(a-b)
    res = x/y/z
    return res

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-x)
    all=all-k
result=int(all)%(7+10**9)
print(result)

Submission status: Runtime Error

Solution code:
H,W,A,B=map(int,input().split())
def kaijo(a):
    x=1
    for i in range(a):
       x=x*(i+1)
    return x
def con(a,b):
    x=kaijo(a)
    y=kaijo(b)
    z=kaijo(a-b)
    res = x/y/z
    return res

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-x)
    all=all-k
print(int(all))