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:
H, W, A, B = map(int, input().split())
answer = 0
mod = 1000000007
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

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

Submission status: Runtime Error

Solution code:
mod = 1000000007
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

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

Submission status: Runtime Error

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

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

# 階乗
for i in range(1, N):
    fac[i] = (fac[i - 1] * i) % MOD
 
# 逆元
inv[N - 1] = pow(fac[N - 1], mod - 2, mod)
for i in range(N - 1, 0, -1):
    inv[i - 1] = (inv[i] * i) % MOD
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

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

Submission status: Runtime Error

Solution code:
import math
const MOD = 1000000007


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


def main():
    H, W, A, B = map(int, input().split())
    nr = 0
    for i in range(1, N - A + 1):
        nr = nr + comb(i - 1, B + i - 2) * comb(m - b - 1, m + n - b - i - 1) % MOD
    print(nr % MOD)

main()

Submission status: Runtime Error

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

import math

H, W, A, B = map(int, input().split())
union_sum = 0
i = 0
for n in range(B, W):
    m = H - A - 1 + n
    tmp_a = math.factorial(m) / (math.factorial(n) * math.factorial(m - n))
    tmp_b = math.factorial(A - B + W - 2 - i) / (math.factorial(A - 1) * math.factorial(W - B  - 1 - i))
    union_sum += tmp_a * tmp_b
    i += 1

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

Submission status: Runtime Error

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

import math

H, W, A, B = map(int, input().split())
union_sum = 0
i = 0
for n in range(B, W):
    m = H - A - 1 + n
    tmp_a = math.factorial(m) / (math.factorial(n) * math.factorial(m - n))
    tmp_b = math.factorial(A - B + W - 2 - i) / (math.factorial(A - 1) * math.factorial(W - B  - 1 - i))
    union_sum += tmp_a * tmp_b
    i += 1

print(int(union_sum))

Submission status: Runtime Error

Solution code:
from scipy.special import comb
h,w,a,b=map(int,input().split())
s=0
for i in range(1,h-a+1):
    s=s+comb(i-2+b,i-1,exact=True)*comb(w-b-1+h-i,w-b-1,exact=True)
print(s%(10**9+7))

Submission status: Runtime Error

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

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

def mycomb(n, k):
    return factorials[n] / (factorials[k] * factorials[n - k])

MOD = int(1e9 + 7)

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

r = 0
for i in range(H - A):
    combination = mycomb(B-1+i, B-1) * mycomb(W+H-B-i-2, W-B-1)
    r += int(combination % MOD)

print(r)

Submission status: Runtime Error

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

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

def mycomb(n, k):
    return factorials[n] / (factorials[k] * factorials[n - k])

MOD = int(1e9 + 7)

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

r = 0
for i in range(H - A):
    combination = mycomb(B-1+i, B-1) * mycomb(W+H-B-i-2, W-B-1)
    r += combination % MOD

print(r)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
isPrime = [True for i in range(100001)]
isPrime[0] = False
isPrime[1] = False

for i in range(2, 100001):
    if isPrime[i]:
        j = 2
        while i*j <= 100000:
            isPrime[i*j] = False
            j += 1

q = int(input())
que = list()
for i in range(q):
    que.append(list(map(int, input().split())))

for a, b in que:
    ans = 0
    for i in range(a, b+1):
        if isPrime[i]:
            if isPrime[(i+1)//2]:
                ans += 1
    print(ans)

Submission status: Runtime Error

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

def nCmRemain(n, m):
    return ((factorial(n)/factorial(n - m))/factorial(m)) % (pow(10,9)+7)

path = np.zeros((A+1, W-B), dtype=np.int)
for i in range(W-B):
    path[0][i] = nCmRemain(H-A+B-1+i,B+i)
for i in range(A+1):
    path[i][0] = path[0][0]
for i in range(1, A+1):
    for j in range(1, W-B):
        path[i][j] = (path[i-1][j] + path[i][j-1]) % (pow(10,9)+7)
print(path[A][W-B-1])

Submission status: Runtime Error

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

p = 10 ** 9 + 7
s = 0

fact = [1]

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

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

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

rfact.reverse()

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

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

print(s%p)

Submission status: Runtime Error

Solution code:
import scipy.misc as scm

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

p = 10 * * 9 + 7
s = 0

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

print(s%p)

Submission status: Runtime Error

Solution code:
import numpy as np

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

nmod = 10**9+7
board = np.zeros((h+1, w+1), dtype=int)
board[1,1] = 1

for x in range(1, h+1):
    for y in range(1, w+1):
        if x >= h-a+1 and y <= b:
            continue
        board[x,y] += board[x-1,y] + board[x,y-1]
        if board[x,y] >= nmod:
            board[x,y] = board[x,y] % nmod
print(board[h,w])

Submission status: Runtime Error

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

mod=10**9+7


FACT={}
FACT_INVERSE={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

#print FACT


def C(n,r):
	return (FACT[n]*pow(FACT[r],10**9+5 ,mod)*pow(FACT[n-r],10**9+5 ,mod)) %mod

N=(H-A-1)+B
M=(H-1)+(W-1)-N

p=0
for i in range(H-A,H):
	#print N,i,M,(H-1)-i,C(N,i), C(M,(H-1)-i)
	p+=C(N,i)*C(M,(H-1)-i)		#Count patterens via prohibited point.
	p=p%mod


if C(N+M,(H-1))-p>=0:
	print C(N+M,(H-1))-p
else:
	print C(N+M,(H-1))-p+10**9+7

Submission status: Runtime Error

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

mod=10**9+7


FACT={}
FACT_INVERSE={}

n=1
for i in range(H+W-1):
	if i==0: n=1
	else: n=(n*i)%mod
	FACT[i]=n

for x,y in FACT.items():
	FACT_INVERSE[x]=pow(FACT[x],10**9+5 ,mod)


def C(n,r):
	return (FACT[n]*FACT_INVERSE[r]*FACT_INVERSE[n-r]) %mod


N=(H-A-1)+B
M=(H-1)+(W-1)-N

p=0
for i in range(H-A,H):
	#print N,i,M,(H-1)-i,C(N,i), C(M,(H-1)-i)
	p+=C(N,i)*C(M,(H-1)-i)		#Count paterens through prohibited point.
	p=p%mod


if C(N+M,(H-1))-p>=0:
	print C(N+M,(H-1))-p
else:
	print C(N+M,(H-1))-p+10**9+7

Submission status: Runtime Error

Solution code:
import sys

debug_mode = True if len(sys.argv) > 1 and sys.argv[1] == "-d" else False
if debug_mode:
    import os
    inf = open(os.path.basename(__file__).replace(".py", ".in"))

    def input():
        return inf.readline()
else:
    inf = sys.stdin

# ==============================================================


def main():
    h, w, a, b = [int(x) for x in input().strip().split()]
    from math import factorial
    r = h - a
    c = w - b
    res = factorial(r + c) / factorial(r) * factorial(c)
    print(res % (10**9 + 7))


main()

# ==============================================================

if debug_mode:
    inf.close()