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: Time Limit Exceeded

Solution code:
H,W,A,B=map(int,input().split())
memo=[[] for i in range(H)]
memo[0]=[1 for i in range(W)]
for i in range(1,H):
	for j in range(W):
		if i>=H-A and j <B:
			memo[i].append(0)
		elif j==0:
			memo[i].append(1)
		else:
			memo[i].append((memo[i-1][j]+memo[i][j-1])%(10**9+7))
print(memo[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
height, width, a, b = [int(i) for i in input().split(' ')]


arrays = [[1] * width for _ in range(height)]

for i in range(-a, 0):
    for j in range(0, b):
        arrays[i][j] = 0

for i in range(height):
    arrays[i] = [0] + arrays[i]

arrays = [[0] + [1] + [0] * (width - 1)] + arrays

for i in range(1, height+1):
    for j in range(1, width+1):
        if arrays[i][j] != 0:
            arrays[i][j] = arrays[i-1][j] + arrays[i][j-1]

answer = arrays[height][width] % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

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

def combinations_count(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

def solve():
    # print(H, W, A, B)

    goal = W - 1, H - 1

    # 境界点
    nx = B - 1
    ny = H - A

    # 境界点から斜め右上の点から, y=0 へ伸びる線が choke point
    c_bottom = nx + 1, ny - 1
    # print(c_bottom)
    choke_points = []
    combs = []

    for i in range(c_bottom[1], -1, -1):
        choke_points.append((c_bottom[0], i))

    for i in range(len(choke_points)):
        x, y = choke_points[i]
        if i == len(choke_points) - 1:
            combs.append(combinations_count(x + y, x))
        else:
            combs.append(combinations_count((x + y) - 1, x - 1))

    for i in range(len(choke_points)):
        x, y = choke_points[i]
        dx, dy = goal[0] - x, goal[1] - y
        combs[i] *= combinations_count(dx + dy, dx)

    # print(sum(combs))
    res = sum(combs) % (10 ** 9 + 7)
    return res
  

res = solve()
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
def f(x,y):
    return fact[x-1+h-y]*fact[y-1+w-x]*inv_fact[x-1]*inv_fact[y-1]*inv_fact[w-x]*inv_fact[h-y]%mod
h,w,a,b = LI()
fact = [1]
for i in range(h+w):
    fact.append(fact[-1]*(i+1)%mod)
inv_fact = [pow(fact[-1],mod-2,mod)]
for i in range(h+w):
    inv_fact.insert(0,inv_fact[0]*(h+w-i)%mod)
ans = 0
for i in range(1,min(w-b,h-a)+1):
    ans += f(b+i,a+i)
    ans %= mod
print(ans)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
import math


def solve(H, W, A, B):
    ans = 0
    R = 10 ** 9 + 7

    p1_y = math.factorial(H - 1 - A)
    d2_y = math.factorial(H - 1 - (H - A))
    way1 = -1
    way3 = -1

    for i in range(0, W - B):
        p1 = (B + i, H - 1 - A)
        p2 = (B + i, H - A)
        e = (W - 1, H - 1)
        d2 = (e[0] - p2[0], e[1] - p2[1])

        if way1 == -1:
            way1 = (math.factorial(p1[0] + p1[1]) // math.factorial(p1[0]) // p1_y)
        else:
            way1 *= (p1[0] + p1[1])
            way1 //= (p1[0])

        if way3 == -1:
            way3 = (math.factorial(d2[0] + d2[1]) // math.factorial(d2[0]) // d2_y)
        else:
            way3 *= (d2[0] + 1)
            way3 //= (d2[0] + d2[1] + 1)
        ans += (way1 % R) * (way3 % R)
    return ans % R

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

Submission status: Time Limit Exceeded

Solution code:
import math

def solve(H, W, A, B):
    ans = 0
    R = 10 ** 9 + 7

    p1_y = math.factorial(H - 1 - A)
    d2_y = math.factorial(H - 1 - (H - A))
    way1 = -1
    way3 = -1

    for i in range(0, W - B):
        p1 = (B + i, H - 1 - A)
        p2 = (B + i, H - A)
        e = (W - 1, H - 1)
        d2 = (e[0] - p2[0], e[1] - p2[1])

        if way1 == -1:
            way1 = (math.factorial(p1[0] + p1[1]) // math.factorial(p1[0]) // p1_y)
        else:
            way1 *= (p1[0] + p1[1])
            way1 //= (p1[0])

        if way3 == -1:
            way3 = (math.factorial(d2[0] + d2[1]) // math.factorial(d2[0]) // d2_y)
        else:
            way3 *= (d2[0] + 1)
            way3 //= (d2[0] + d2[1] + 1)
        ans += (way1 % R) * (way3 % R)
    return ans % R

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

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
fac = [1 for _ in range(10**6+1)]
for i in range(1, 10 **6):
    fac[i+1] = fac[i] * (i + 1)

def combination(n, r):
    result = fac[n] // (fac[r] * fac[n-r])
    return result

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

Submission status: Time Limit Exceeded

Solution code:
H,W,A,B=map(int,input().split())
power=[]
for tate in range(H):
    x= []
    for yoko in range(W):
        x.append(0)
    power.append(x)
power[0][0]+=1
def calc(power,x,y):
    if y==0 and x==0:return power
    if y==0:ue=0
    if y!=0:ue=power[y-1][x]
    if x==0:hidari=0
    if x!=0:hidari=power[y][x-1]
    if y>=H-A and x < B:
        power[y][x]=0
    if y<H-A or x >=B:
        power[y][x]=ue+hidari
    return power
for y in range(H):
    for x in range(W):
        power=calc(power,x,y)
result= power[H-1][W-1]%(7+10**9)
print(result)

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = map(int, input().split())
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for k in range(1, H + W):
    for y in range(max(H, W)):
        x = k - y
        if 0 <= y < H and 0 <= x < W:
            if y < H - A or B <= x:
                if x - 1 >= 0:
                    dp[y][x] += dp[y][x - 1]
                if y - 1 >= 0:
                    dp[y][x] += dp[y - 1][x]
MOD = 1000000007
print(dp[H - 1][W - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    
H,W,A,B=map(int,raw_input().split())

Corner=[[B+i,A+i] for i in range(1,min(W-B,H-A)+1)]
Result=0
for c in Corner:
    Result+=combinations_count(c[0]-1+H-c[1],c[0]-1)*combinations_count(W-c[0]+c[1]-1,c[1]-1)
print Result%(10**9+7)

Submission status: Time Limit Exceeded

Solution code:
# calculate N!(modP)
def fac(n):
    ans = 1
    mod = 10**9+7
    for i in range(1, n+1):
        ans *= i
        ans %= mod
    return ans
 
# calculate a**b(modP)     
def cal(a, b, mod):
    if b == 0:
        return 1
    elif b % 2 == 0:
        return cal(a, b//2, mod)**2 % mod
    else:
        return (a * cal(a, b-1, mod)) % mod 
    
H, W, A, B = map(int, input().split())

ans = 0
mod = 10**9+7


for w in range(B, W):
    now = fac((H-A-1)+w) * cal(fac(H-A-1), mod-2, mod) * cal(fac(w), mod-2, mod) % mod
    now *= fac((A-1)+(W-w-1)) * cal(fac(A-1), mod-2, mod) * cal(fac(W-w-1), mod-2, mod) % mod
    ans = (ans+now) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = 10 ** 9 + 7

def pow_K(x, n):
  if n == 0:
    return 1
  else:
    return (pow_K(x, n // 2) ** 2 * x ** (n % 2)) % K

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

fact = [0 for i in range(H+W-1)]
fact[0] = 1
for i in range(H+W-2):
  fact[i + 1] = fact[i] * (i+1) % K
fact_inv = [pow_K(fact[i], K-2) for i in range(H+W-1)]

r = 0
for i in range(B, W):
  r += ((fact[H-A-1+i] * fact_inv[H-A-1] %K)*fact_inv[i] % K) * ((fact[W-1-i+A-1] * fact_inv[W-1-i] %K) * fact_inv[A-1] % K) %K
  r %= K

print(r)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def P(n, r):
    return factorial(n)//factorial(n-r)

def C(n, r):
    return P(n, r)//factorial(r)


ans = 0
H,W,A,B = map(int, input().split())
MOD = int(1e9)+7

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import math

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

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

def solve():
    ans = 0
    an = H + B - A - 1
    ar = B
    bn = W + A - B - 2
    br = W - B - 1
    for i in range(W-B):
        a = comb(an, ar)
        b = comb(bn, br)
        ans += a * b
        an += 1; ar += 1
        bn -= 1; br -= 1
    return ans%(10**9+7)

print(solve())

Submission status: Time Limit Exceeded

Solution code:
iH,iW,iA,iB = [int(x) for x in input().split()]
iD = 1000000007

def fFr(iX,iR=1):
    if iR == 0 or iX == 0:
        return 1
    else :
        iRet = 1
        for i in range(iR,iX+1):
            iRet *= i
        return iRet

def fnCr(iN,iR):
    if iR == 0:
        return 1
    else:
        return fFr(iN,iR+1) // fFr(iN-iR)

iRet = 0
for iL in range(0,iH-iA):
    iRet += (fnCr(iL+iB-1,iL) * fnCr(iW-iB+iH-iL-2,iW-iB-1))%iD
    iRet %= iD
iRet %= iD
print(iRet)

Submission status: Time Limit Exceeded

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

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

# 予め組み合わせ計算に必要な階乗のテーブルを作っておく
factorials = [0] * (H+W)
factorials[0] = 1
factorials[1] = 1
for i in range(2,H+W):
    factorials[i] = factorials[i-1] * i
    
# 組み合わせの数だけ返してくれる関数(自作)
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorials[n]
    # 分母の計算
    denominator = factorials[r] * factorials[n-r]
    return numerator // denominator

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % (10 ** 9 + 7)
    h -= 1
    w += 1

print(ans)

Submission status: Time Limit Exceeded

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

# 組み合わせの数だけ返してくれる関数
def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

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

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans += nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h) % (10 ** 9 + 7)
    h -= 1
    w += 1

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

Submission status: Time Limit Exceeded

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

from itertools import combinations as comb

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

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans += len(list(comb([0] * (h+w-2), h-1))) * len(list(comb([0] * (H-h+W-w), H-h))) % (10 ** 9 + 7)
    h -= 1
    w += 1

print(ans)

Submission status: Time Limit Exceeded

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

from itertools import combinations as comb

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

HW = len(list(comb([0] * (H+W-2), H-1)))

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans += len(list(comb([0] * (h+w-2), h-1))) * len(list(comb([0] * (H-h+W-w), H-h))) % (10 ** 9 + 7)
    h -= 1
    w += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W,A,B=inpl()
ans = 0

def Comb(n,k):#nCk
	gyakugen = [1]*(n+1)
	fac = [1]*(n+1)

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

	for i in range(n,0,-1):
		gyakugen[i-1] = (gyakugen[i]*i)%mod
	com = [1]*(n+1)

	for i in range(1,n+1):
		com[i] = (fac[n]*gyakugen[i]*gyakugen[n-i])%mod

	return com[k]%mod

for x1 in range(B+1,W+1):
	y1 = H-A
	x2 = A
	y2 = W-x1+1
	ans += (Comb(x1+y1-2,y1-1)*Comb(x2+y2-2,y2-1))%mod
	ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(c, r):
    return mod_pow(fc[c] * fc[r] % m, m - 2, m)

import functools
@functools.lru_cache(maxsize=None)
def cr(c, r):
    return fc[c + r] * rev(c, r) % m

ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1) % m
print(ans % m)

Submission status: Time Limit Exceeded

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

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

import functools
@functools.lru_cache(maxsize=None)
def rev(c, r):
    return mod_pow(fc[c] * fc[r] % m, m - 2, m)

def cr(c, r):
    return fc[c + r] * rev(c, r) % m


ans = 0
for c in range(B, W):
    ans = (ans + cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)) % m
print(ans)

Submission status: Time Limit Exceeded

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

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(n):
    return mod_pow(n, m - 2, m)

def cr(c, r):
    return fc[c + r] * rev(fc[c] * fc[r] % m) % m


ans = 0
for c in range(B, W):
    ans = (ans + cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)) % m
print(ans)

Submission status: Time Limit Exceeded

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

m = 10**9 + 7

fc = [1] * (H + W)
for i in range(2, H+W):
    fc[i] = fc[i - 1] * i % m

import functools
@functools.lru_cache(maxsize=None)
def fact(n):
    if n == 0: return 1
    return n * fc[n - 1] % m

def mod_pow(x, n, mod):
    if n == 0: return 1
    d, m = n >> 1, n & 1
    p = mod_pow(x, d, mod)
    return (p * p * (x if m else 1)) % mod

def rev(n):
    return mod_pow(n, m - 2, m)

def cr(c, r):
    return fact(c + r) * rev(fact(c) * fact(r) % m) % m


ans = 0
for c in range(B, W):
    ans += cr(c, H - 1 - A) * cr(W - 1 - c, A - 1)
print(ans % m)

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = map(int,input().split())
P = 10**9+7
#H, W, A, B = map(int,"100000 100000 44444 55555".split())

factlist = [1] * (H+W)
t = 1
for i in range(H+W-1):
	t = (t * (i+1)) % P
	factlist[i+1] = t

def fact(i):
	return factlist[i]

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

s = 0
i = 0
while H-A-i-1 >= 0 and B+i <= W and A+i <= H and W-B-i-1 >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
H, W, A, B = map(int, input().split())
p = 10 ** 9 + 7
ans = 0
def fac(a, b):
  a = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
  return a % p
for h in range(H - A):
  ans += fac(h, B - 1) * fac(H - h - 1, W - B - 1) % p
print(ans % p)

Submission status: Time Limit Exceeded

Solution code:
# E.py#
H, W, A, B = map(int,input().split())
P = 10**9+7
# H, W, A, B = map(int,"2 3 1 1".split())

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def fact(i):
	t = 1
	while i > 0:
		t = (t * i) % P
		i -= 1
	return t

def comb(i,j):
	return (fact(i+j) * modinv(fact(i),P) * modinv(fact(j),P)) % P

s = 0
i = 0
while H-A-i > 0 and B+i+1 <= W and A+i <= H and W-B-i >= 0:
#	print((H-A-i,B+i+1))
	s = (s + comb(H-A-i-1,B+i+1-1) * comb(A+i,W-B-i-1)) % P
	i += 1	
print(s)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
from math import factorial
h, w, a, b = list(map(int, input().split()))
num_path = 0

def get_path(n, r):
    return factorial(n)//(factorial(n-r)*factorial(r))

y, x = h-a, b+1
while(True):
    path_0 = get_path((y+x-2), min(x-1, y-1))
    path_1 = get_path((h-y+w-x), min(h-y, w-x))
    # print(y, x, path_0, path_1)
    num_path = (num_path + path_0*path_1)%MOD

    y -= 1
    x += 1
    if y == 0 or x > w:
        break
    
print(num_path)

Submission status: Time Limit Exceeded

Solution code:
h, w, lower_bound, left_bound = map(int, input().split())

grid = [[0 for i in range(w)] for j in range(h)]

lower_i = h - lower_bound
left_i = left_bound

for i in range(lower_i, len(grid)):
  for j in range(0, left_i):
    grid[i][j] = 1

def count_path(row, col, grid, memo):
  if memo[row][col] != -1:
    return memo[row][col]

  path_count = 0
  if grid[row][col] == 1:
    memo[row][col] = 0
    return memo[row][col]

  if row == h-1 and col == w-1:
    return 1

  if row+1 < len(grid):
    path_count += count_path(row+1, col, grid, memo)
  if col+1 < len(grid[0]):
    path_count += count_path(row, col+1, grid, memo)

  memo[row][col] = path_count
  return memo[row][col]

path_count = 0
memo = [[-1 for i in range(w)] for j in range(h)]
path_count += count_path(0, 0, grid, memo)
final_path_count = path_count % (pow(10, 9) + 7)
print(final_path_count)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H,W,A,B = map(int, input().split())
ans = 0
for i in range(H-A):
  L1 = [j for j in range(B+i-1)]
  L2 = [k for k in range(H+W-B-i-2)]
  C1 = list(itertools.combinations(L1,i))
  C2 = list(itertools.combinations(L2,W-B-1))
  ans += (len(C1) * len(C2)) %(10**9 + 7)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
LIM = 10**9 + 7


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

    print(solve(h, w, a, b))


def solve(h, w, a, b):
    ans = 0
    for i in range(h-a):
        first = n_noblock_fast(i + 1, b) % LIM
        second = n_noblock_fast(w - b, h - i) % LIM
        ans = (ans + (first * second) % LIM) % LIM
    return ans


def n_noblock_fast(h, w):
    return choose(h + w - 2, w - 1)

def n_noblock(h, w):
    n_paths = [[0 for _ in range(w)] for _ in range(h)]
    # Accessed with n_paths[ih, iw],
    # where ih is height, and iw is horizontal position.

    for ih in range(h):
        n_paths[ih][0] = 1

    for iw in range(w):
        n_paths[0][iw] = 1

    for ih in range(1, h):
        for iw in range(1, w):
            n_paths[ih][iw] += n_paths[ih-1][iw]
            n_paths[ih][iw] += n_paths[ih][iw-1]

    #return n_paths[h-1][w-1]
    return n_paths


def choose(n, k):
    return factorial(n) // factorial(k) // factorial(n-k)


def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i + 1)

    return ans

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(h):
    for j in range(w):
        if i>h-a-1 and j<b:
            continue
        if i-1>=0:
            road[i][j]+=road[i-1][j]
        if j-1>=0:
            if i>h-a-1 and j==b:
                continue
            road[i][j]+=road[i][j-1]
print(road[h-1][w-1]%1000000007)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
l = list(map(int,input().split()))
h,w,a,b = l[0],l[1],l[2],l[3]
def pow(x,n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res*x % MOD
        x = x*x % MOD
        n = n >> 1
    return res

def comb(n,k):
    return (fact[n]*inv[k] % MOD)*inv[n-k] % MOD

fact = [1]
inv = [1]
for i in range(h+w):
    fact.append(fact[i]*(i+1) % MOD)
    inv.append(pow(fact[i+1],MOD-2) % MOD)
ans = 0
for i in range(w-b):
    ans = (ans + (comb(h-a+b+i-1,b+i)*comb(w-b-i+a-2,a-1) % MOD)) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

M = 10**9+7
def nCr(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

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

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

print(ans % M)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def sub(a,b):
  return (a-b) % MOD

def mul(a,b):
  return ((a%MOD) * (b%MOD)) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

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

factorical = [1]
factorical_inv = [1]
for n in range (1,H+W+1):
  f = mul(factorical[-1], n)
  factorical.append(f)
  factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

def add(a,b):
  return (a+b) % MOD

def sub(a,b):
  return (a-b) % MOD

def mul(a,b):
  return ((a%MOD) * (b%MOD)) % MOD

def pow(a,n):
  ans = 1
  mag = a
  for b in reversed(str(bin(n))):
    if b == 'b': break
    if b == '1':
      ans = mul(ans, mag)
    mag = mul(mag, mag)
  return ans

def inv(a):
  return pow(a, MOD-2)

factorical = [1]
factorical_inv = [1]
for n in range (1,200002):
  f = mul(factorical[-1], n)
  factorical.append(f)
  factorical_inv.append(inv(f))

def ncr(n,r):
  return mul(mul(factorical[n], factorical_inv[n-r]), factorical_inv[r])

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

def paths(w,h):
  return ncr(w+h,w)

ans = 0
for i in range(W-B):
  p = mul(paths(H-A-1, B+i), paths(A-1, W-B-1-i))
  ans = add(ans, p)
print ans

Submission status: Time Limit Exceeded

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

def comb(x,y):
  return(math.factorial(x)//(math.factorial(x-y)*math.factorial(y)))

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

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

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = [int(x) for x in input().split()]
matrix = [[0 for x in range(W)] for y in range(H)]
matrix[0][0] = 1
for y in range(0, H):
    for x in range(0, W):
        # if not (y >= H-A and x < B):
        if y < H-A or x >= B:
            if y != 0:
                matrix[y][x] += matrix[y-1][x]
            if x != 0:
                matrix[y][x] += matrix[y][x-1]
ans = divmod(matrix[H-1][W-1], pow(10,9) + 7)
print(ans[1])

Submission status: Time Limit Exceeded

Solution code:
import math
class Paths:
	def returnPaths(self,h,w,a,b):
		ans=0
		dic={}
		for i in range(h+w): dic[i]=math.factorial(i)
		for i in range(b,w): 
			checkpoint=dic[h-a-1+i]/(dic[h-a-1]*dic[i])
			ans+=checkpoint*(dic[a-2+w-i]/(dic[a-1]*dic[w-1-i]))
			ans%=10**9+7
		print ans

if __name__ == "__main__":
	h,w,a,b=[int(i) for i in raw_input().split()]
	p=Paths()
	p.returnPaths(h,w,a,b)

Submission status: Time Limit Exceeded

Solution code:
def POW(a,b,MOD):
    p = 1
    while b > 0:
        if b&1:
            p = p*a%MOD
        b >>= 1
        a = (a*a)%MOD
    return p

MOD = int(1e9+7)
H,W,A,B = map(int,input().split())


fact = [1] * (H+W+1)
inv = [1] * (H+W+1)
for i in range(H+W):
    fact[i+1] = (i+1)*fact[i]%MOD
    inv[i+1] = POW(fact[i+1],MOD-2,MOD)


ans = 0

for i in range(B,W):
    temp = fact[H-A-1+i]
    temp = (temp*inv[H-A-1])%MOD
    temp = (temp*inv[i])%MOD

    temp = (temp*fact[A-1 + W-i-1])%MOD
    temp = (temp*inv[A-1] )%MOD
    temp = (temp*inv[W-i-1])%MOD
    ans = (ans+temp)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re


class IO_for_Contest(object):
    @staticmethod
    def my_input():
        # return raw_input()
        return input()

    @staticmethod
    def read_from_input():
        pass

    @staticmethod
    def read_line():
        return IO_for_Contest.my_input().strip()

    @staticmethod
    def read_int():
        return int(IO_for_Contest.my_input().strip())

    @staticmethod
    def read_n_int(n):
        return list(map(
            int,
            re.split('\s+', IO_for_Contest.my_input().strip())))[: n]


def solve():
    h, w, a, b = IO_for_Contest.read_n_int(4)
    board = prepare_board(h, w)
    ways = count_ways(board, a, b)
    print(ways)


def prepare_board(h, w):
    board = []
    for y in range(h):
        board.append([0] * w)
    return board


def count_ways(board, a, b):
    mode = 10 ** 9 + 7
    board[0][0] = 1
    h = len(board)
    w = len(board[0])
    for y in range(h):
        for x in range(w):
            if x == 0 and y == 0:
                continue
            if is_prohibited(w, h, b, a, x, y):
                board[y][x] = 0
                continue
            ways_on_left_cell = get_ways_on_cell(board, x - 1, y)
            ways_on_upper_cell = get_ways_on_cell(board, x, y - 1)
            board[y][x] = (ways_on_left_cell + ways_on_upper_cell) % mode
            # print('{0:d}, {1:d} = {2:d}'.format(x, y, board[y][x]))
    # print(board)
    return board[h - 1][w - 1]


def get_ways_on_cell(board, x, y):
    if x < 0:
        return 0
    if y < 0:
        return 0
    return board[y][x]


def is_prohibited(w, h, b, a, x, y):
    return (x < b) and (y >= h - a)

if __name__ == '__main__':
    # import doctest
    # doctest.testmod()
    solve()

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = map(int, input().split())
#masu = [[0 for x in range(10)] for y in range(10)]
masu = [[0 for j in range(W)] for i in range(H)]

for j in range(W):
	masu[0][j] = 1

for i in range(H-A):
	masu[i][0] = 1

for i in range(1, H-A):
	for j in range(1, W):
		masu[i][j] = (masu[i-1][j] + masu[i][j-1]) % 1000000007

for i in range(H-A, H):
	for j in range(B, W):
		masu[i][j] = (masu[i-1][j] + masu[i][j-1]) % 1000000007

print(masu[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7;F=[pow(X,M-2,M)for X in range(8**6)];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: Time Limit Exceeded

Solution code:
import functools;M=10**9+7;F=functools.lru_cache(2**16)(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: Time Limit Exceeded

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)%M*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

Submission status: Time Limit Exceeded

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)*(H-I)*F(I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

Submission status: Time Limit Exceeded

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(W-1-B):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)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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