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:
import math

def nCr(n, r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

def solv(H, W, A, B):
    h = H - 1
    w = W - 1

    total = nCr(h+w, h)

    i = h - A
    forbidden = 0
    for j in range(B):
        forbidden += nCr(i+j, i) * nCr((h-i-1)+(w-j), h-i-1)

    return int(total - forbidden)


H, W, A, B = [int(i) for i in input().split()]

res = solv(H, W, A, B)
print(res)

Submission status: Wrong Answer

Solution code:
mod=1000000007
#mod=1777777777
pi=3.141592653589
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

h,w,a,b=map(int,raw_input().split())
t=pscl(h-1+w-1)[w-1]
d=pscl(a-1+b-1)[a-1]
print (t-d)%mod

Submission status: Wrong Answer

Solution code:
import math

def c_calc(a,b):
    return math.factorial(a)/math.factorial(a-b)/math.factorial(b)

def math_calc(h,w):
    return c_calc(h-1+w-1,h-1)

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

    all_ans = 0
    for x in range(B+1,W+1):
        all_ans += math_calc(H-A,x) * math_calc(A,W-x+1)

    print all_ans

Submission status: Wrong Answer

Solution code:
h, w, a, b = map(int, raw_input().split())
mod = 10**9+7
ans = 0
mod_fact = [1]
for i in range(1,h+w-2):
    mod_fact.append((i*mod_fact[i-1])%mod)
factinv = [1] * (h+w-2)
factinv[h+w-3] = pow(mod_fact[h+w-3],(mod-2),mod)
for i in reversed(range(2,h+w-3)):
    factinv[i] = (factinv[i+1] * (i+1))%mod
def C(n,r):
    return mod_fact[n]*factinv[r]*factinv[n-r]%mod
for i in range(b,w):
    ans += C(i+h-a-1,h-a-1) * C(a-1+w-i-1,a-1) % mod
print ans

Submission status: Wrong Answer

Solution code:
import itertools,math,bisect,pprint,sys
h, w, a, b = map(int, raw_input().split())
mod = 10**9+7
ans = 0
def mod_fact(n):
    res = 1
    for i in range(1,n+1):
        res *= i
        res %= mod
    return res
def divmod(n):
    return pow(mod_fact(n),(mod-2),mod)
def C(n,r):
    return mod_fact(n)*divmod(n-r)*divmod(r)%mod
for i in range(b,w):
    ans += C(i+h-a-1,h-a-1) * C(a-1+w-i-1,a-1) % mod
print ans

Submission status: Wrong Answer

Solution code:
H,W,A,B = [int(n) for n in input().split(" ")]
answers = []
for total in range(B,W):
    disp,div = 1,1
    for n in range(min(H-A,total + 1),total+(H-A)):
        if div >= max(H-A,total + 1):
            disp = (disp * n) % (10**9 + 7)
        else:
            disp = ((disp * n) % (10**9 + 7) // div)
            div += 1
    answers.append(disp%( 10 ** 9 + 7))

for cnt,total in enumerate(range(B,W)):
    disp,div = 1,1
    for n in range(min(H- (H - A),W-total),(W - total - 1) + (H - (H - A))):
        if div >= max(H- (H - A),W-total):
            disp = (disp * n) % (10**9 + 7)
        else:
            disp = ((disp * n )% (10**9 + 7) // div)
            div += 1
    answers[cnt] *= disp%( 10 ** 9 + 7)
print(sum(answers) %( 10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import math

def nCr(n, r):
    return (int(math.factorial(n)) // int(math.factorial(r)) // int(math.factorial(n - r))) % C

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

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

print(ans % C)

Submission status: Wrong Answer

Solution code:
import math

def nCr(n, r):
    return (int(math.factorial(n)) // int(math.factorial(r)) // int(math.factorial(n - r))) % C

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

row = [nCr(i + h - a - 1, h - a - 1) for i in range(b, w)]
row2 = reversed([nCr(i, i - b) for i in range(b, w)])

ans = sum([x * y for x, y in zip(row, row2)])

print(ans % C)

Submission status: Wrong Answer

Solution code:
H,W,A,B = [int(n) for n in input().split(" ")]
answers = []
for total in range(B,W):
    disp = 1
    for n in range(1,total+(H-A)):
        disp *= n
    for m in range(1,H-A ):
        disp //= m
    for t in range(1,total + 1):
        disp //= t
    answers.append(disp)
for cnt,total in enumerate(range(B,W)):
    disp = 1
    for n in range(1,(W - total - 1) + (H - (H - A))):
        disp  *= n
    for m in range(1,H- (H - A)):
        disp //= m
    for t in range(1,W-total):
        disp //= t
    answers[cnt] *= disp
print(sum(answers))

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
H, W, A, B = map(int, raw_input().split())
dp = [1]*W
b = 1
for h in xrange(H-1):
    print dp
    if h == H-A-1:
        print "!"
        dp = dp[B:]
    for w in xrange(1, len(dp)):
        dp[w] += dp[w-1]%MOD

print dp[-1]

Submission status: Wrong Answer

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

m = [1 for _ in range(w)]

for _ in range(h - a - 1):
	for j in range(1, w):
		m[j] = m[j] + m[j - 1]

for _ in range(a):
	for j in range(b + 1, w):
		m[j] = m[j] + m[j - 1]	

print m[w - 1]

Submission status: Wrong Answer

Solution code:
h, w, a, b = map(int, raw_input().split())
m = [[0 for i in range(w)] for j in range(h)]

for i in range(a):
	for j in range(b):
		m[h - i - 1][j] = -1

for i in range(w):
	m[0][i] = 1

for i in range(h - a):
	m[i][0] = 1

for i in range(a):
	m[h - i - 1][b] = 1

for i in range(1, h):
	for j in range(1, w):
		if m[i][j] != -1 and m[i][j - 1] != -1:
			m[i][j] = m[i - 1][j] + m[i][j - 1]
		if m[i][j] != -1 and m[i][j - 1] == -1:
			m[i][j] = m[i - 1][j]

print m[h - 1][w - 1]

Submission status: Time Limit Exceeded

Solution code:
# H, W, A, Bの入力受付
H, W, A, B = map(int, input().split())
# 2次元リストの要素に上のマスと左のマスにある数字を足した数を順次代入
MAP = []
for i in range(H):
    if i != 0 and i <= (H - A - 1):
        # 2行目以降の1列目には1を入力する
        MAP.append([1])
    else:
        # 1行目と下からAマス以内には0を入力する
        MAP.append([0])
    for j in range(W):
        # 1列目には1を既に入力している
        if j == 0:
            continue
        # 1行目の2列目以降には1を入力する
        elif i == 0:
            MAP[i].append(1)
        # 下からAマス、左からBマス以内には0を入力する
        elif i > (H - A - 1) and j <= (B -1):
            MAP[i].append(0)
        # それ以外では左の値と上の値を加算したものを入力する
        else:
            MAP[i].append(MAP[i-1][j] + MAP[i][j-1])
# 場合の数を指定の数値で割った値を出力
print(MAP[H-1][W-1] % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def dfs(x,y):
    global ans
    if not(0<=x<h) or not(0<=y<w) or maze[x][y]=='#':
        return
    if maze[x][y]=='g':
        ans += 1
        return
    dfs(x+1,y)
    dfs(x,y+1)

h,w,a,b = map(int,input().split())
maze = [['.' for i in range(w)] for j in range(h)]
for i in range(1,a+1):
    for j in range(b):
        maze[-i][j] = '#'
maze[-1][-1]='g'
#for i in range(h):
#    print(maze[i])

ans = 0
dfs(0,0)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w,a,b = map(int,input().split())
dp = np.array([[1] * w] * h)
dp[h-a:,:b] = 0
for i in range(1,h-a):
    for j in range(1,w):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10 ** 9 + 7)
for i in range(h-a,h):
    for j in range(b,w):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % (10 ** 9 + 7)
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

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


# def cmb(n, r):
#     r = min(n-r, r)
#     if r == 0:
#         return 1
#     over = reduce(mul, range(n, n - r, -1))
#     under = reduce(mul, range(1, r + 1))
#     return over // under


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

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

mod = 10**9 + 7

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

print(int(res) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

kei=math.factorial(h+w-2)//(math.factorial(h-1)*math.factorial(w-1))
cc=0
for i in range(a):
    c=math.factorial(h-1+b-i-1)//(math.factorial(b-1)*math.factorial(h-i-1))
    bc=math.factorial(w-b-1+i)//(math.factorial(i)*math.factorial(w-b-1))
    cc+=c*bc
ans=kei-cc
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def combi(n, r):
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

Submission status: Time Limit Exceeded

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

p=10**9+7
#p=127

def modp_factorial(n):
    s=1
    for x in range(1,h+1):
        s=(s*x) % p
    return s
def modp_prod(lst):
    s=1
    for x in lst:
        s=(s*x)%p
    return s
def inv(n):
    s=1
    q=p-2
    while q>0:
        if q&1:
            s=s*n % p
        n=n*n
        q>>=1
    return s

l=[1]
f=1
for x in range(1,h+w+1):
    f=f*x % p
    l.append(f)
invl=[inv(l[-1])]
for n in range(h+w,1,-1):
    invl.append((invl[-1]*n) % p)
invl.append(1)
invl.reverse()


s=0
for x in range(1,h-a+1):
    s=s+modp_prod([l[x+b-2],invl[x-1],invl[b-1]\
        ,l[w-b+h-x-1],invl[h-x],invl[w-b-1]])% p
print(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def _main():
    h, w, a, b = get_ints()

    from collections import defaultdict

    dd = defaultdict(lambda: 1)

    for i in range(1, h-a):
        for j in range(1, w):
            dd[j] = dd[j] + dd[j - 1]

    for i in range(h-a, h):
        for j in range(b+1, w):
            dd[j] = dd[j] + dd[j - 1]

    print(dd[w-1] % (10**9 + 7))


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys
from collections import defaultdict

  
def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def _main():
    h, w, a, b = get_ints()

    list2 = defaultdict(int)
    for j in range(0, w):
        list2[0, j] = 1
    for i in range(1, h-a):
        list2[i, 0] = 1
    for i in range(1, h-a):
        for j in range(1, w):
            list2[i, j] = list2[i - 1, j] + list2[i, j - 1]
    for i in range(h-a, h):
        list2[i, b] = list2[i-1, b]
    for i in range(h-a, h):
        for j in range(b+1, w):
            list2[i, j] = list2[i - 1, j] + list2[i, j - 1]

    print(list2[h-1, w-1] % (10**9 + 7))


if __name__ == "__main__":
    _main()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        return power(a, b//2, p) ** 2 % p
    else:
        return power(a, b//2, p) ** 2 * a % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007
b = power(factorial(B-1), p-2, p)
d = power(factorial(D-1), p-2, p)

x = 0
for i in range(C):
    k = factorial(i+B-1) % p
    l = factorial(D+H-i-2) % p
    x += (k * l * b * d * power(factorial(i), p-2, p) * power(factorial(H-i-1), p-2, p)) % p
print(x % p)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        x = power(a, b//2, p)
        return x ** 2 % p
    elif b % 2 == 1:
        y = power(a, b-1, p)
        return a * y % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007
b = power(factorial(B-1), p-2, p)
d = power(factorial(D-1), p-2, p)

x = 0
for i in range(C):
    k = factorial(i+B-1) % p
    l = factorial(D+H-i-2) % p
    x += (k * l * b * d * power(factorial(i), p-2, p) * power(factorial(H-i-1), p-2, p)) % p
print(x % p)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        x = power(a, b//2, p)
        return x ** 2 % p
    elif b % 2 == 1:
        y = power(a, b-1, p)
        return a * y % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007
b = power(factorial(B-1), p-2, p)
d = power(factorial(D-1), p-2, p)

x = 0
for i in range(C):
    k = factorial(i+B-1) % p
    l = factorial(D+H-i-2) % p
    x += k * l * b * d * power(factorial(i), p-2, p) * power(factorial(H-i-1), p-2, p)
print(x % p)

Submission status: Time Limit Exceeded

Solution code:
def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        x = power(a, b//2, p)
        return x ** 2 % p
    elif b % 2 == 1:
        y = power(a, b-1, p)
        return a * y % p

def comb(a, b, p): #(a+b)!/a!b! (mod p)を求める #power関数を使う
    from math import factorial
    if a<0 or b<0:
        return 0
    if a==0 or b==0:
        return 1
    A = factorial(a)
    B = factorial(b)
    AB = factorial(a+b)
    return (AB * power(A,p-2,p) * power(B,p-2,p)) % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007

x = 0
for i in range(C):
    x += (comb(i, B-1, p) * comb(D-1, H-i-1, p)) % p
print(x % p)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import*
from sys import *
import sys
sys.setrecursionlimit(10**7)


@lru_cache(None)
def f(n):
    if n < 2:
        return 1
    else:
        return n * (f(n - 1))


MOD = 10**9 + 7


def c(a, b):
    return (f(a) // (f(b) * f(a - b))) % MOD


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

Submission status: Time Limit Exceeded

Solution code:
h,w,a,b=map(int, input().split())
mod=1000000007
matx=[[0 for y in range(w)] for x in range(h)]
for j in range(w):
    matx[0][j]=1
for i in range(h-a):
    matx[i][0]=1
for i in range(h-a):
    for j in range(w):
        matx[i][j]=(matx[i-1][j]+matx[i][j-1])%mod
for i in range(h-a, h):
    for j in range(b, w):
        matx[i][j]=(matx[i-1][j]+matx[i][j-1])%mod
print(matx[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
# a^n mod p
def beki_mod(a, n, p):
    ans = 1
    n = format(n, "b")
    for i in range(len(n)):
        ans = ans * ans % p
        if n[i] == "1":
            ans = ans * a % p
    return ans

# a! mod p
def kaijo_mod(a, p):
    ans = 1
    while a > 0:
        ans = ans * a % p
        a -= 1
    return ans    

# nCr = n * (n -1) * ... * (n - r + 1) / r!
# a^(-1) mod p = a^(p -2) mod p
def combi_mod(n, r, p):
    bunshi = 1
    r = min(r, n - r)

    bumbo = kaijo_mod(r, p)
    bumbo_gyakugen = beki_mod(bumbo, p - 2, p)

    while r > 0:
        bunshi = bunshi * n % p
        n -= 1
        r -= 1
    
    ans = bunshi * bumbo_gyakugen % p
    return ans


H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans += n
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans += n
    ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# a^n mod p
def beki_mod(a, n, p):
    ans = 1
    n = format(n, "b")
    for i in range(len(n)):
        ans = ans * ans % p
        if n[i] == "1":
            ans = ans * a % p
    return ans

# nCr = n * (n -1) * ... * (n - r + 1) / r!
# a^(-1) mod p = a^(p -2) mod p
def combi_mod(n, r, p):
    bunshi = 1
    bumbo_gyakugen = 1
    r = min(r, n - r)

    while r > 0:
        bunshi = bunshi * n % p
        bumbo_gyakugen = bumbo_gyakugen * beki_mod(r, p - 2, p) % p
        n -= 1
        r -= 1
    
    ans = bunshi * bumbo_gyakugen % p
    return ans


H, W, A, B = map(int, input().split())
mod = 10 ** 9 + 7

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans += n
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans += n
    ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def conbi(n, r):
    bunbo = 1
    bunshi = 1
    if n / 2 < r:
        r = n - r
    while r > 0:
        bunbo *= r
        bunshi *= n
        r -= 1
        n -= 1
    return bunshi // bunbo

def conbi_mod(n, r):
    return conbi(n, r) % (10 ** 9 + 7)
    


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

if B < W / 2:
    not_ans = 0
    total = conbi_mod((H - 1) + (W - 1), H-1)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h -1) + (sq1w - 1), (sq1h -1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        not_ans += n
    ans = (total - not_ans) % (10 ** 9 + 7)
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h - 1) + (sq1w - 1), (sq1h - 1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        ans += n
    ans = ans % (10 ** 9 + 7)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

H, W, A, B = map(int, input().split())
count = 0
mid_point_yoko = B-1
end_point_yoko = W-B-1
for i in range(1,H-A+1):
    mid_point_total = i + B - 2

    end_point_total = W-B-1+H-i
    
    mid_point = combinations_count(mid_point_total, mid_point_yoko)
    end_point = combinations_count(end_point_total, end_point_yoko)
    #print(mid_point,end_point)
    count += mid_point*end_point

#print(count)
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def numberOfWays(h, w, a, b):
  dp = [0] * h
  for i in range(h):
    dp[i] = [0] * w
  for i in range(h):
    if h - a > i:
      dp[i][0] = 1 
  for j in range(w):
    dp[0][j] = 1
  for i in range(1, h):
    for j in range(1, w):
      if h - a > i or b <= j:
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  return dp[-1][-1]
  
h, w, a, b = map(int, input().split())
print(numberOfWays(h, w, a, b) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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

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

a=B-1
b=H+N-2
c=N-1
max1=H+W
fact=math.factorial(max1)
mod=fact%(10**9+7)
mod_inv=mod**(10**9+5)%(10**9+7)
list1=[[max1mod,max1mod_inv]]
for i in range(max1):
  fact=fact//(max1-i)%(10**9+7)
  mod=fact%(10**9+7)
  mod_inv=mod_inv*(max1-i-1)
  list1.append([mod,mod_inv])
  

S=sum((list1[max1-a-k][0]*list1[max1-a][1]*list1[max1-k][1]*list1[max1-b+i][0]*list1[max1-c][1]*list1[max1-b+i+c][1])%(10**9+7)for k in range(M))
print(S%(10**9+7))

Submission status: Time Limit Exceeded

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

judge = (A+B)/(H+W)
a = H-A
res = 0

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


if judge < 0.5:
    base = comba(H+W-2, W-1)
    for i in range(1,B+1):
        ex1 = comba(a-1+i-1,i-1)
        ex2 = comba(A-1+W-i,W-i)
        exres = ex1 *ex2
        res = res + exres
        result = (base -res) %1000000007

else:
    for i in range(1,H-A+1):
        ex1 = comba(i-1+B-1,i-1)
        ex2 = comba(W-B-1+H-i,H-i)
        exres = ex1 *ex2
        res = res + exres
        result = res %1000000007

print(result)

Submission status: Time Limit Exceeded

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

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

base = comba((H+W-2), W-1)

for i in range(1,B+1):
    ex1 = comba(a-1+i-1,i-1)
    ex2 = comba(A-1+W-i,W-i)
    exres = ex1 *ex2
    res = res + exres

result = (base -res) %1000000007
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

from collections import deque

per = 10**9 + 7

goal_cnt = 0
que = deque([])
que.append((0, 0))

while que:
    p = que.popleft()
    if p[0] == H-1 and p[1] == W-1:
        goal_cnt += 1
        goal_cnt %= per
    else:
        for vh, vw in [[1, 0], [0, 1]]:
            pos_h = p[0] + vh
            pos_w = p[1] + vw
            
            if 0 <= pos_h <= H-1 and 0 <= pos_w <= W-1 and not(pos_w <= B-1 and pos_h >= H - A):
                que.append((pos_h, pos_w))
print(goal_cnt)

Submission status: Time Limit Exceeded

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

from collections import deque

field = [[0 if w <= B-1 and h >= H - A else 1 for w in range(W)] for h in range(H)]

goal_cnt = 0
que = deque([])
que.append((0, 0))

while que:
    p = que.popleft()
    if p[0] == H-1 and p[1] == W-1:
        goal_cnt += 1
        goal_cnt %= 10**9 + 7
    else:
        for vh, vw in [[1, 0], [0, 1]]:
            pos_h = p[0] + vh
            pos_w = p[1] + vw
            
            if 0 <= pos_h <= H-1 and 0 <= pos_w <= W-1 and field[pos_h][pos_w] == 1:
                que.append((pos_h, pos_w))
print(goal_cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections, math, bisect

local = False
if local:
    file = open("input.txt", "r")
    import time

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]


if local:
    start=time.time()

#H==rows
#W==cols

H,W,A,B = ints()

grid = [0 for c in range(W)]

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

for i in range(1, H):
    for j in range(W):
        if j+1<=B and i>=H-A:
            grid[j] = 0
            continue

        left = top = 0

        if j>0:
            left = grid[j-1]

        grid[j] = (left+grid[j])

print(grid[W-1]%(10**9+7))


if local:
    fin = (time.time()-start)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Time Limit Exceeded

Solution code:
import math
import time

DIV_VALUE = 10**9 + 7

def calcModOfPow(a, n, p):
    btm = a
    ans = 1
    while n != 0:
        # print('btm: {}'.format(btm))
        if n & 1:
            ans = (ans * btm) % p
            # print('ans: {}'.format(ans))
        n = n>>1
        btm = (btm**2) % p
        # print(n)

    return ans

class FirstHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.sup = 0
        self.numOfCases = 1

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                (self.B + self.k - 1)
            ) * (
                calcModOfPow(self.k, DIV_VALUE-2, DIV_VALUE)
            ) % DIV_VALUE
        self.k += 1
        # print('----- k == {} -----'.format(self.k))
        # print(self.numOfCases)
        # self.numOfCases %= DIV_VALUE
        return self.numOfCases
        # return self.numOfCases % DIV_VALUE

class SecondHalf:
    def __init__(self, H, W, A, B):
        self.H = H
        self.W = W
        self.A = A
        self.B = B
        self.k = 0
        self.div = 0
        self.numOfCases = 1
        totalval = self.H + self.W - self.B - 2
        loopval = self.H - 1 if self.H < self.W - self.B else self.W - self.B - 1
        for top in range(totalval, totalval - loopval, -1):
            self.numOfCases *= top
            self.numOfCases %= DIV_VALUE
        for bottom in range(loopval, 0, -1):
            self.numOfCases *= calcModOfPow(
                bottom,
                DIV_VALUE-2,
                DIV_VALUE
            )
            self.numOfCases %= DIV_VALUE

        # self.numOfCases = (
        #     math.factorial(self.H + self.W - self.B - 2)
        # ) // (
        #     math.factorial(self.W - self.B - 1)
        # ) // (
        #     math.factorial(self.H - 1)
        # )

    def getNumOfCases(self):
        if self.k != 0:
            self.numOfCases = self.numOfCases * (
                self.H - self.k
            ) * (
                calcModOfPow(
                    self.H + self.W - self.B - self.k - 1,
                    DIV_VALUE-2,
                    DIV_VALUE
                )
            ) % DIV_VALUE
        self.k += 1
        # print(self.numOfCases)
        # self.numOfCases %= DIV_VALUE
        return self.numOfCases
        # return self.numOfCases % DIV_VALUE

if __name__ == '__main__':
    [H, W, A, B] = [int(ipt) for ipt in input().split()]
    
    start = time.time()
    fstHlf = FirstHalf(H, W, A, B)
    sndHlf = SecondHalf(H, W, A, B)
    totalCases = 0

    mid = time.time()
    # print('mid: {}'.format(mid - start))
    for _ in range(H - A):
        totalCases += (
            fstHlf.getNumOfCases() * sndHlf.getNumOfCases()
        )
        totalCases %= DIV_VALUE

    end = time.time()
    # print('end: {}'.format(end - mid))
    print(totalCases)

    #print('{} {} {} {}'.format(H, W, A, B))
    #print(DIV_VALUE)

    # for i in range(12):
    #     print(calcModOfPow(i+1, 3, 13))
    # print(calcModOfPow(3, 13))

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = list(map(int, input().split(' ')))
def move(i, j, H, W, A, B):
    grid = [[0 for i in range(W)] for j in range(H)]
    
    for i in range(H-A):
        grid[i][0] = 1
    for i in range(W):
        grid[0][i] = 1
    # print(grid)
    for i in range(1, H):
        for j in range(1, W):
            # print(grid)
            upper = 0
            try:
                upper = grid[i-1][j]
            except:
                pass
            left = 0
            try:
                left = grid[i][j-1]
            except:
                pass
            if (i >= (H-A) and j < B):
                continue
            else:
                grid[i][j] = upper + left
    return grid[H-1][W-1]
    

ways = move(1, 1, H, W, A, B)
print(ways % (10**9 + 7))