Problem:


Score : 400 points

Problem Statement

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

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

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

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

Constraints

 1 ≦ H, W ≦ 100,000

 1 ≦ A < H

 1 ≦ B < W

Input

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

H W A B

Output

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

Sample Input 1

2 3 1 1

Sample Output 1

2

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

Sample Input 2

10 7 3 4

Sample Output 2

3570

There are 12 forbidden cells.

Sample Input 3

100000 100000 99999 99999

Sample Output 3

1

Sample Input 4

100000 100000 44444 55555

Sample Output 4

738162020



Sample input:
2 3 1 1


Sample output:
2

Submission status: Wrong Answer

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

MOD = 10**9 + 7

def count_dr(d,r):
    # H+WCW
    cnt = 1
    multiple_nums = list(range(d+r,d,-1))
    divide_nums = list(range(1,r+1))
    for num in multiple_nums:
        cnt *= num % MOD
        
    for num in divide_nums:
        cnt = cnt // num
    
    return cnt

def zouka_combination(zouka,kotei,how_many):
    tmp = count_dr(zouka,kotei)
#     print(tmp)
#     tmp_last = count_dr(a,w-b-1)
    result = []
    for i in range(1,how_many+1):
        numer = zouka+kotei+i
        denom = zouka+i
        tmp *= numer
        tmp //= denom
        result.append(tmp)
    return result

exit = zouka_combination(H-A-1,B-1,A)
last = ([1] + zouka_combination(0,W-B-1,A-1))[::-1]

cnt = 0
for e, l in zip(exit,last):
    cnt += e*l
    cnt %= MOD
print(count_dr(H-1,W-1) - cnt)

Submission status: Wrong Answer

Solution code:
import math

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

H,W,A,B=map(int,input().split())
f=[1]
M=10**9+7
for i in range(1,H+W):
  f.append(f[i-1]*i%M)
ans=0
for i in range(B,W):
  aa=(f[H-A-1+i]//(f[H-A-1] * f[i]))%M
  bb=(f[A+W-2-i]//(f[A-1]*f[W-1-i]))%M
  cc=(aa*bb)%M
  ans+=cc
  ans%=M
print(ans)

Submission status: Wrong Answer

Solution code:

mod = 10**9+7


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


class Fact():
    def __init__(self, H, W):
        self.mod = 10**9+7
        self.facts = [1]*(H+W-1)
        for i in range(1, H+W-1):
            self.facts[i] = self.facts[i-1]*i % mod

        self.i = [pow(self.facts[-1], mod-2, mod)]
        for i in range(1, H+W-1)[::-1]:
            self.i.append(self.i[-1]*i % mod)
        self.i.reverse()

    def comb(self, n, r):
        ret = self.facts[n] * self.i[n-r]*self.i[r]
        return ret

    def print_fact(self):
        print(self.facts)


f = Fact(H, W)

all_path = f.comb(H+W-2, H-1)

f.print_fact()

remove_path = 0
for i in range(B):
    tmp = f.comb(H-A+i-1, i)
    tmp *= f.comb(W-i-1+A-1, A-1)
    remove_path += tmp

remove_path %= mod

print((all_path - remove_path) % mod)

Submission status: Wrong Answer

Solution code:
def comb(n, r):
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n
    ret = 1
    for i in range(r):
        ret *= (n-i)/(r-i)
        ret %= mod
    return int(ret)


mod = 10**9+7


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

all_path = comb(H+W-2, H-1)

remove_path = 0
for i in range(B):
    tmp = comb(H-A+i-1, i)
    tmp *= comb(W-i-1+A-1, A-1)
    remove_path += tmp

remove_path %= mod
print((all_path - remove_path) % mod)

Submission status: Wrong Answer

Solution code:
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
    
def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

h,w,a,b=map(int, input().split())
mod=10**9+7
c=0
for i in range(h-a):
    c+=comb(b+i-1,i,mod)*comb(h+w-b-2-i,w-b-1,mod)
print(c)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2

# print('{}C{} * {}C{}'.format(aa + b, b , a + bb -1, bb))

ans %= mod
for i in range(1, bb+1):
    # ans += nCb(aa+b+i, b+i) * nCb(a+bb-1-i, bb-i)
    c1 = c1 * (aa + b + i) // (b + i)
    c2 = c2 * (bb - i + 1) // (a + bb - i)
    ans += c1 * c2
    ans %= mod

    # print('{}C{} * {}C{}'.format(aa+b+i, b+i, a+bb-1-i, bb-i))

print(ans%mod)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2

ans %= mod
for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) // (b + i)
    c2 = c2 * (bb - i + 1) // (a + bb - i)
    ans += c1 * c2
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
ans = 0
c1 = nCb(b-1,0)
c2 = nCb(w-b+h-2, h-1)
for i in range(h-a):
    ans += c1 * c2
    ans %= mod
    c1 = c1 * (b+i) // (i+1)
    c2 = c2 * (h-i-1) // (w-b+h-i-2)
print(ans)

Submission status: Wrong Answer

Solution code:
BIG = 10 ** 9 + 7

def fact(n):
	f = 1
	for i in range(1, n + 1):
		f = int((f * i) % BIG)
	return f

def comb(n, r):
	return int(fact(n) / ((fact(n - r) * fact(r)) % BIG))

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

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod 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) 
  c=factorial(n-k) 
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
 
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
 
H,W,A,B=map(int, input().split())
p=10**9+7
alls=comb(H+W-2,W-1,10**9+7)
for i in range(B):
  alls-=comb(H-A-1+i,H-A-1,p)*comb(W+A-2-i,A-1,p)
 
print(alls)

Submission status: Wrong Answer

Solution code:
def comb(n,k,p):
  """power_funcを用いて(nCk) mod 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):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

H,W,A,B=map(int, input().split())
p=10**9+7
alls=comb(H+W-2,W-1,10**9+7)
for i in range(B):
  alls-=comb(H-A-1+i,H-A-1,p)*comb(W+A-2-i,A-1,p)

print(alls)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return permutations(n,m)
def citer(n,m):
    return combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    if a-b < b:
        b = a-b
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

###########

h,w,a,b = ii()
s = 0
for i in xrange(h-a):
    s += ((modc(i+b-1,b-1,10**9+7) % (10**9+7)) * (modc(h-i+w-b-2,h-i-1,10**9+7) % (10**9+7))) % (10**9+7)
print s

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return permutations(n,m)
def citer(n,m):
    return combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

###########

h,w,a,b = ii()
s = 0
for i in xrange(h-a):
    s += ((modc(i+b-1,b-1,10**9+7) % (10**9+7)) * (modc(h-i+w-b-2,h-i-1,10**9+7) % (10**9+7))) % (10**9+7)
print s

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int
sys.setrecursionlimit(1000000)


def cumsum(lis, val=0, result=[]):
    if not lis:
        return result
    l, *others = lis
    return cumsum(
        others, val + l, result + [val + l]
    )


def row_update(row, depth, result=[]):
    if not depth:
        return result
    cumsum_row = cumsum(row)
    return row_update(
        cumsum_row, 
        depth - 1, 
        result + [row]
    )


def solve_left_top(height, width):
    row = [1] * height
    return row_update(row, width)[-1]


def solve_right_top(row, width):
    result = row_update(row, width + 1)
    return [r[-1] for r in result][1:]


def solve_right_bottom(row, height):
    result = row_update(row, height + 1)
    return result[-1][-1]


def solve(H: int, W: int, A: int, B: int):
    row = solve_left_top(H - A, B)
    row = solve_right_top(row, W - B)
    answer = solve_right_bottom(row, A)
    print(answer % MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def powmod(a, n, mod):
    p = 1
    while n > 0:
        if n % 2 == 0:
            a = a**2 % mod
            n /= 2
        else:
            p *= a
            p %= mod
            n -= 1
    return p


def invmod(a, mod):
    return powmod(a, mod-2, mod)


def combmod(n, k, mod):
    if n < k : return 0
    else:
        if n < 2*k: k = n-k
        bunsi = fac[n]
        bunbo = inv[k] * inv[n-k]
        return bunsi * bunbo % mod

fac = [1] * (H+W+1)
inv = [1] * (H+W+1)
for i in range(H+W+1):
    if i == 0:
        fac[i] = 1
        inv[i] = 1
    else:
        fac[i] = fac[i-1] * i % INF
        inv[i] = inv[i-1] * invmod(i, INF) % INF

ans = 0
for i in range(min(W, H - A + B) - B):
    h = H - A - i
    w = B + 1 + i
    ans += combmod(h+w-2, h-1, INF) * combmod(H+W-h-w, H - h, INF) % INF

print(ans%INF)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from scipy.misc import comb
mod=10**9+7
h,w,a,b=map(int,input().split())
ans=0
for i in range(b,w):
    ans=(ans+comb(h-a-1+i,i,exact=1)*comb(a-1+w-i-1,w-i-1,exact=1))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

H,W,A,B=map(int,input().split())
f=[1]
for i in range(1,100001):
  f.append(f[i-1]*i)
M=10**9+7
ans=0
for i in range(B,W):
  a=comb(H-A-1+i,i)%M
  b=comb(A+W-2-i,W-1-i)%M
  c=(a*b)%M
  ans+=c
  ans%=M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
H,W,A,B=map(int,input().split())
M=10**9+7
ans=0
for i in range(B,W):
  a=comb(H-A-1+i,i)%M
  b=comb(A+W-2-i,W-1-i)%M
  c=(a*b)%M
  ans+=c
  ans%=M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
H,W,A,B=map(int,input().split())
M=10**9+7
t=[1]
s=[1]
for i in range(1,H-A):
  t.append(comb(i+B-1,B-1)%M)
  s.append((t[i]+s[i-1])%M)

for i in range(H-A,H):
  s.append(s[-1])
for i in range(B+1,W):
  u=[1]
  for j in range(1,H):
    u.append((s[j]+u[j-1])%M)
  s=u[:]
print(s[-1])

Submission status: Time Limit Exceeded

Solution code:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

#n! = a p^eとしたときのeを求める (O(logp n)
def mod_e(n,p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res

#n! = a p^eとしたときのa mod pを求める  (O(logp n)
def mod_fact(n,p):
    if n==0:
        return 1
    
    
    res = mod_fact(n//p,p)
    
    if n//p %2 != 0:
        return res*(p-fact[n%p])%p
    return res*fact[n%p]%p
    
######################################################

#nCk mod p
def mod_comb(n,k):
    if n < 0 or k < 0 or n<k:
        return 0
    e1 = mod_e(n,p)
    e2 = mod_e(k,p)
    e3 = mod_e(n-k,p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n,p)
    a2 = mod_fact(k,p)
    a3 = mod_fact(n-k,p)
    return a1 * mod_inv(a2*a3%p,p) %p
######################################################

h,w,a,b = map(int,input().split())
#pは素数とする
p = 10**9+7
#fact[i] : i! modp (0<= i <p) O(p)
fact = [1]
k = 1
for i in range(1,10**6+100):
    k = k*i%p
    fact.append(k)

res = 0
for i in range(h-a):
    res += mod_comb(i+b-1,b-1)*mod_comb(h-i-1+w-b-1,w-b-1)
    res = res%p
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import functools

MOD = 1000000007
fact = []

def main():
    h, w, a, b = map(int, input().split())
    init_fact(200000, MOD)
    mp = get_list_middle_points(h, w, a, b)
    res = 0
    for y, x in mp:
        res += count(1, 1, x, y) * count(x, y, w, h)
        res %= MOD
    print(res)

def count(x1, y1, x2, y2):
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    count = combi(dx + dy, dx, MOD)
    return count

def get_list_middle_points(h, w, a, b):
    li = []
    y = h - a
    x = b + 1
    while (y >= 1 and x <= w):
        li.append((y, x))
        y -= 1
        x += 1
    return li

def combi(n, k, mod):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % mod
    return (numera * inv(denomi, mod)) % mod

def init_fact(maxn, mod):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % mod)

def inv(n, mod):
    return pow(n, mod - 2, mod)

def pow(n, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2, mod)
        return (x * x) % mod
    else:
        x = pow(n, p - 1, mod)
        return (x * n) % mod

main()

Submission status: Time Limit Exceeded

Solution code:
ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2

ans %= mod
for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) * inv(b + i)
    c2 = c2 * (bb - i + 1) * inv(a + bb - i)
    ans += c1 * c2
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


def inv(x):
    return pow(x, mod - 2, mod)


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2


ans %= mod
for i in range(1, bb+1):
    ans += nCb(aa+b+i, b+i) * nCb(a+bb-1-i, bb-i)   
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
BIG = (10 ** 9) + 7

f_list = [1] * 200000
f_r_list = [1] * 200000

for i in range(199999):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % BIG)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % BIG), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % BIG)

for i in range(200000):
	f_r_list[i] = power(f_list[i], BIG - 2)

def comb(n, r):
	if n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % BIG) * f_r_list[r - 1]) % BIG 

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

ans = 0

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

print(int(ans))

Submission status: Time Limit Exceeded

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

from scipy.misc import comb


def _(n):
    return n % (10**9 + 7)


def main():
    H, W, A, B = list(map(int, input().split(' ')))
    ANS = 0
    for i in range(B, W):
        c1 = comb(H - A - 1 + i, i, 1)
        c2 = comb(A - 1 + W - i - 1, W - i - 1, 1)
        ANS = _(ANS + _(c1) * _(c2))
    print(ANS)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, max_fact, mod):
        #mod should be prime number
        #using homogeneous_product(n,r), max_fact ≧ max(n+r-1)
        f = [1] * (max_fact + 1)
        for idx in range(2, max_fact + 1):
            f[idx] = f[idx - 1] * idx
            f[idx] %= mod
        if mod > max_fact:
            fi = [pow(f[-1], mod - 2, mod)]
            for idx in range(max_fact, 0, -1):
                fi += [fi[-1] * idx % mod]
            fi = fi[::-1]
        else:
            fi = [pow(n, mod - 2, mod) for n in f]
        self.mod = mod
        self.f = f
        self.fi = fi

    def factorial(self, n):
        return self.f[n]

    def factorial_inverse(self, n):
        return self.fi[n]

    def combination(self, n, r):
        f = self.f
        fi = self.fi
        return f[n] * fi[r] * fi[n - r] % self.mod

    def permutation(self, n, r):
        return self.f[n] * self.fi[n - r] % self.mod

    def homogeneous_product(self, n, r):
        f = self.f
        fi = self.fi
        return f[n + r - 1] * fi[r] * fi[n - 1] % self.mod


max_fact = 2 * 10 ** 6
mod = 10**9 + 7
fact_instance = Factorial(max_fact, mod)
comb = fact_instance.combination
perm = fact_instance.permutation
combrep = fact_instance.homogeneous_product

H, W, A, B = [int(_) for _ in input().split()]
ans = comb(H + W - 2, H - 1)
for x in range(H - A, H):
    ans -= comb(x + B - 1, B - 1) * comb(H - 2 - x + W - B, W - B - 1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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

#############
# Main Code #
#############

lim = 10 ** 6 + 1
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

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

H, W, A, B = getNM()

mother = cmb((H - 1) + (W - 1), (W - 1))

goban = cmb((H - A) + (B - 1), B - 1)
togoal = cmb((A - 1) + (W - B - 1), (W - B - 1))

for i in range(A):
    row = H - A + i
    col = B - 1
    row_left = A - 1 - i
    col_left = W - B - 1
    mother -= cmb(row + col, row) * cmb(row_left + col_left, row_left)
    mother %= mod
print(mother)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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


M = 10**9+7 # 出力の制限
N = h+w+10 # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

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

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

Submission status: Accepted

Solution code:
SIZE=2*10**5; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    fac[i] = fac[i-1]*i%MOD
finv[-1] = pow(fac[-1],MOD-2,MOD)
for i in range(SIZE-1,0,-1):
    finv[i-1] = finv[i]*i%MOD
    inv[i] = finv[i]*fac[i-1]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0


# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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


ans = 0
for r in range(0,h-a):
    ans += choose(b-1+r,b-1)*choose(w-b-1+h-r-1,w-b-1)

print(ans%MOD)

Submission status: Accepted

Solution code:
H, W, A, B = map(int, input().split())
mod = 10**9+7
facs = [1] * (H+W+1)
invs = [1] * (H+W+1)
nfac = 1
for i in range(1, H+W+1):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

def combs(n, r):
    return facs[n] * invs[r] * invs[n-r] % mod

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

print(ans)

Submission status: Accepted

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


class Combination:
    """
    Usage：
    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):
        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):
        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


mod = 10 ** 9 + 7
comb = Combination(h+w, mod)

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

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 1000000007
class Combination(object):
    def __init__(self, N, MOD):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        # 前計算
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    Com = Combination(H+W, MOD)
    ans = 0
    for i in range(B, W):
        ans += Com.com((H-A-1)+i, i) * Com.com((A-1)+(W-i-1), A-1)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, n - 1)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.mod


def solve():
    H, W, A, B = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    com = Combination(H + W, MOD)
    ans = 0
    for i in range(B, W):
        tmp = com.ncr(i + H - A - 1, i)
        tmp = tmp * com.ncr(W - i - 1 + A - 1, W - i - 1) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h,w,a,b=map(int,input().split())
mod=10**9+7
N=10**6
ans=0
def comb(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
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 )
for i in range(1,h-a+1):
  ans=(ans+comb(b+i-2,i-1,mod)*comb(h+w-b-i-1,w-b-1,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

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

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 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())
r = 0
for i in range(H-a):
    r = (r + mul(cmb(b-1+i, i), cmb(W-b-1+H-i-1, W-b-1))) % mod
print(r)