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:
MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            self.inverses.append(mod_inverse(i, self.mod))
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


def d_cmb(n, r, mod):
    return mod_cmb(n + r - 1, r, mod)


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


n1 = A - 1
r1 = A - 1
n2 = W + (H - A - 1) - 1
r2 = H - A - 1
temp = d_cmb(W, H - A - 1, MOD) * d_cmb(1, 0, MOD)
ans = temp
for _ in range(1, W - B):
    temp = temp * (n1 + 1) * mod_inverse(n1 + 1 - r1, MOD) % MOD
    temp = temp * (n2 - r2) * mod_inverse(n2, MOD) % MOD
    n1 += 1
    n2 -= 1
    ans = (ans + temp) % MOD

print(ans)

Submission status: Time Limit Exceeded

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


n1 = B + H - A - 1
r1 = H - A - 1
n2 = W + A - B - 2
r2 = A - 1
temp = mod_cmb(n1, r1, MOD) * mod_cmb(n2, r2, MOD) % MOD
ans = temp
for _ in range(1, W - B):
    temp = temp * (n1 + 1) * mod_inverse(n1 + 1 - r1, MOD) % MOD
    temp = temp * (n2 - r2) * mod_inverse(n2, MOD) % MOD
    n1 += 1
    n2 -= 1
    ans = (ans + temp) % MOD

print(ans)

Submission status: Time Limit Exceeded

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


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


n1 = B + H - A - 1
r1 = H - A - 1
n2 = W + A - B - 2
r2 = A - 1
temp = mod_cmb(n1, r1, MOD) * mod_cmb(n2, r2, MOD) % MOD
ans = temp
for _ in range(1, W - B):
    temp = temp * (n1 + 1) * mod_inverse(n1 + 1 - r1, MOD) * (n2 - r2) * mod_inverse(n2, MOD) % MOD
    n1 += 1
    n2 -= 1
    ans = (ans + temp) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
h,w,a,b= list(map(int, input().split()))
m=1000000007
ans=0
a1=(factorial(h-a+b-1))//(factorial(h-a-1)*factorial(b))
a2=(factorial(w-b+a-2))//(factorial(a-1)*factorial(w-b-1))
ans+=a1*a2
ans%=m
for i in range(1,w-b):
    a1=a1*(h-a+b+i-1)//(b+i)
    a2=a2*(w-b-i)//(w-b-i+a-1)
    tmp=a1*a2%m
    ans+=tmp
    ans%=m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
h,w,a,b= list(map(int, input().split()))
m=1000000007
ans=0
# a1=(factorial(h-a+b+i-1))//(factorial(h-a-1)*factorial(b+i))
# a2=(factorial(w-b-i+a-2))//(factorial(a-1)*factorial(w-b-i-1))
for i in range(w-b):
    if i==0:
        a1=(factorial(h-a+b+i-1))//(factorial(h-a-1)*factorial(b+i))
        a2=(factorial(w-b-i+a-2))//(factorial(a-1)*factorial(w-b-i-1))
    else:
        a1=a1*(h-a+b+i-1)//(b+i)
        a2=a2*(w-b-i)//(w-b-i+a-1)
    ans+=a1*a2
    ans%=m
print(ans)

Submission status: Time Limit Exceeded

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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

h,w,a,b = map(int,input().split())
res = 0
kai = min(w-b,h-a)
mod = 10**9+7

cmb1 = cmb(h-a-1+b,b) 
cmb2 = cmb(a+w-b-1,a) 
combi = cmb1 * cmb2 
res = combi

for i in range(1,kai):
    combi = (combi *(h-a-i)*(w-b-i))//((b+i)*(a+i))
    res += combi
    res %= mod

print(int(res))

Submission status: Time Limit Exceeded

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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

h,w,a,b = map(int,input().split())
res = 0
kai = min(w-b,h-a)
for i in range(0,kai):
    res += (cmb(h-a-1+b,b+i) * cmb(a+w-b-1,a+i) ) % (10**9+7)
    if res  > 10**9+7:
        res %= 10**9+7

print(res)

Submission status: Time Limit Exceeded

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

res = []
for i in range(0,h):
    res.append([0 for i in range(w)])

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

for j in range(1,h):
    res[j][0] = 1

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

for i in range(1,h):
    for j in range(1,w):
        if res[i][j] == -1:
            continue
        elif res[i][j-1] == -1:
            res[i][j] = res[i-1][j]
        else:
            res[i][j] = res[i-1][j] + res[i][j-1]
            if res[i][j] > 10**9+7:
                res[i][j] %= 10**9+7

print(res[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
h,w,a,b=map(int,input().split())
dp=[[1]*w]+[[1]+[0]*(w-1) for _ in range(h-1)]
for i in range(h-a,h):
  dp[i]=[-1]*b+[0]*(w-b)
for i in range(1,h):
  for j in range(1,w):
    if dp[i][j]==-1:
      continue
    if dp[i][j-1]==-1:
      dp[i][j]=dp[i-1][j]
      continue
    dp[i][j]=dp[i-1][j]+dp[i][j-1]
    dp[i][j]%=1000000007
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,a,b=LI()
  l=[[-1]*(w+1) for _ in range(h+1)]

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

  for i in range(h+1):
    l[i][0]=0

  l[0][1]=1

  for i in range(a):
    for j in range(b):
      l[h-i][b]=-2

  q=queue.Queue()
  q.put((1,1))

  # for x in l:
  #   print(' '.join([str(y) for y in x]))

  while not q.empty():
    a,b=q.get()

    # print(a,b,l[a][b])

    if l[a][b]!=-1:
      continue

    if l[a][b-1]==-2:
      l[a][b]=l[a-1][b]
      l[a][b]%=mod
    else:
      l[a][b]=l[a-1][b]+l[a][b-1]
      l[a][b]%=mod

    if a==h and b==w:
      # break
      return l[a][b]

    for i,j in [(0,1),(1,0)]:
      if a+i<0 or b+j<0 or a+i>h or b+j>w:
        continue

      if l[a+i][b+j]==-1:
        # print(a+i,b+j)
        q.put((a+i,b+j))

  # for x in l:
  #   print(' '.join([str(y) for y in x]))

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

H, W, A, B = map(int, input().split())
ans = 0
root = factorial((H-A-1) + (W-1)) // (factorial(H-A-1) * factorial(W-1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
h, w, a, b = map(int, input().split(" "))
count = 0
for inter_h in range(h - a):
    molec = math.factorial(b - 1 + inter_h)
    denom = math.factorial(b - 1) * math.factorial(inter_h)
    comb_1 = molec // denom
    molec = math.factorial(w - b - 1 + h - inter_h - 1)
    denom = math.factorial(w - b - 1) * math.factorial(h - inter_h - 1)
    comb_2 = molec // denom
    count += (comb_1 * comb_2) % (10 ** 9 + 7)
rem = count % (10 ** 9 + 7)
print(rem)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(w)] for _ in range(h)]
block = [[True for _ in range(w)] for _ in range(h)]

for y in range(h-1, h-a-1, -1):
    for x in range(b):
        block[y][x] = False

dp[0][0] = 1

for i in range(1, h):
    if block[i][0]:
        dp[i][0] = dp[i-1][0]
for i in range(1, w):
    if block[0][i]:
        dp[0][i] = dp[0][i-1]

for y in range(1, h):
    for x in range(1, w):
        if block[y][x]:
            dp[y][x] = (dp[y-1][x] + dp[y][x-1]) % MOD

#print(block, dp)
print(dp[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
H,W,A,B=map(int,input().split())
# H,W,A,B=10,7,3,4
# H,W,A,B=100000,100000,44444,55555
array=[[0 for i in range(W)] for j in range(H)]

#S->P->G の実装
#与えられたHとWで最大値を算出
# ue=math.factorial( H-1 + W-1 )
# sita=math.factorial( H-1 )*math.factorial( W-1 )
# result = ue//sita
# print(result)
# print("---------------")
ans=[]
mod = 10**9+7
#S->PとP->Gの実装
for i in range(0,H-A):
    ue=math.factorial( H-i-1 + W-B-1 )
    sita=math.factorial( H-i-1 )*math.factorial( W-B-1 )
    result1 = ue//sita

    ue=math.factorial( i + B-1)
    sita=math.factorial(i)*math.factorial(B-1)
    result2 = ue // sita
    # print("S->P",result1)
    # print("P->G",result2)
    # print("S->P->G",result1*result2)
    ans.append(result1*result2)

# ue=math.factorial( H-A-1 + W-B-1 )
# sita=math.factorial( H-A-1 )*math.factorial( W-B-1 )
# result = ue//sita
# print("S->P",result)

# ue=math.factorial( A + B-1)
# sita=math.factorial(A)*math.factorial(B-1)
# result = ue // sita
# print("P->G",result)

print(sum(ans)%mod)
# print(*array,sep="\n")
# print(array[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
# H,W,A,B=map(int,input().split())
# H,W,A,B=10,7,3,4
H,W,A,B=100000,100000,44444,55555
# array=[[0 for i in range(W)] for j in range(H)]

#S->P->G の実装
#与えられたHとWで最大値を算出
# ue=math.factorial( H-1 + W-1 )
# sita=math.factorial( H-1 )*math.factorial( W-1 )
# result = ue//sita
# print(result)
# print("---------------")
ans=[]
mod = 10**9+7
#S->PとP->Gの実装
for i in range(0,H-A):
    ue=math.factorial( H-i-1 + W-B-1 )
    sita=math.factorial( H-i-1 )*math.factorial( W-B-1 )
    result1 = ue//sita

    ue=math.factorial( i + B-1)
    sita=math.factorial(i)*math.factorial(B-1)
    result2 = ue // sita
    # print("S->P",result1)
    # print("P->G",result2)
    # print("S->P->G",result1*result2)
    ans.append(result1*result2)

# ue=math.factorial( H-A-1 + W-B-1 )
# sita=math.factorial( H-A-1 )*math.factorial( W-B-1 )
# result = ue//sita
# print("S->P",result)

# ue=math.factorial( A + B-1)
# sita=math.factorial(A)*math.factorial(B-1)
# result = ue // sita
# print("P->G",result)

print(sum(ans)//mod)
# print(*array,sep="\n")
# print(array[H-1][W-1])

Submission status: Time Limit Exceeded

Solution code:
h,w,a,b=[int(i) for i in input().split()]
p=10**9+7
kkk={}
def kai(n):
  if n in kkk:
    return kkk[n]
  a=1
  for i in range(1,n+1):
    a*=i
    a%=p
  kkk[n]=a
  return a
def conv(k,n):
  a=kai(n)*pow(kai(k),p-2,p)*pow(kai(n-k),p-2,p)
  return a%p
ans=0
for i in range(b+1,w+1):
  ans+=conv(i-1,i+h-a-2)*conv(w-i,a+w-i-1)
  ans%=p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,a,b=[int(i) for i in input().split()]
p=10**9+7
def kai(n):
  a=1
  for i in range(1,n+1):
    a*=i
    a%=p
  return a
def conv(k,n):
  a=kai(n)*pow(kai(k),p-2,p)*pow(kai(n-k),p-2,p)
  return a%p
ans=0
for i in range(b+1,w+1):
  ans+=conv(i-1,i+h-a-2)*conv(w-i,a+w-i-1)
  ans%=p
print(ans)

Submission status: Time Limit Exceeded

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

h,w,a,b=map(int,input().split())
amari = 10**9+7

#1.境界まで行く順路のパターン数を求める
l1 = [0 for i in range(w-b)]
for i in range(len(l1)):
    l1[i]=nCr((h-a-1)+b+i,b+i)
#2.境界の1コ下からゴールまで行く順路のパターン数を求める
l2 = [0 for i in range(w-b)]
for i in range(len(l2)):
    l2[i]=nCr((a-1)+(w-b-i-1),a-1)

out= 0 
for i,j in zip(l1,l2):
    #print(i*j)
    out += i*j

print(out%amari)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def pow_mod(x, p):
    res = 1
    while p:
        if p % 2:
            res = res * x % MOD
        x = x * x % MOD
        p //= 2
    return res


F = [1]
invF = [1]


def comb_mod(n, r):
    return F[n] * invF[r] * invF[n - r] % MOD


for i in range(1, H + W - 1):
    F.append(F[-1] * i % MOD)
    invF.append(pow_mod(F[-1], 10 ** 9 + 5))

res = 0
for i in range(B + 1, W + 1):
    p = H - A - 1
    q = i - 1

    res = (
                  res
                  + comb_mod(H - A - 1 + i - 1, H - A - 1)
                  * comb_mod(A - 1 + W - i, W - i)
          ) % MOD

print(res)

Submission status: Time Limit Exceeded

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

grid=[[0]*(w+1) for _ in range(h+1)]
grid[1][1]=1

for x in range(1,w+1):
  for y in range(1,h+1):
    if x>b or y<h-a+1:
      grid[y][x]=grid[y][x]+grid[y-1][x]+grid[y][x-1]
    
print(grid[y][x]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
H, W, A, B = [int(_) for _ in input().split()]
p = 10 ** 9 + 7


# 二分累乗法 で n^x % p を求める
# pow(n,x,p) で得られるので次からはそっちつかう
def power(n, x, p):
    a = n  # a^(2^0), a^(2^1), ...
    ans = 1
    while x > 0:
        if x & 1:
            ans = (ans * a) % p
        x = x >> 1
        a = (a ** 2) % p
    return ans


def solve():
    kaijo = [0] * (H + W + 1)
    kaijo[0] = kaijo[1] = 1
    for i in range(2, H + W + 1):
        kaijo[i] = (i * kaijo[i - 1]) % p
    gyaku = [0] * (H + W + 1)
    gyaku[0] = gyaku[1] = 1
    for i in range(2, H + W + 1):
        gyaku[i] = power(kaijo[i], p - 2, p)

    # for i in range(H + W + 1):
    #     assert (kaijo[i] * gyaku[i]) % p == 1, (kaijo[i], gyaku[i])

    def conb(_x, _y):
        return (kaijo[_x] * gyaku[_y] * gyaku[_x - _y]) % p

    # h = H - A - 1
    # h2 = H - (H - A)
    ans = 0
    for i in range(W - B):
        ans = (ans + conb(H - A - 1 + B + i, H - A - 1) * conb(A - 1 + W - 1 - B - i, A - 1)) % p
    # for i in range(B, W):
    #     tmp1 = kaijo[h + i] * gyaku[h + i] * gyaku[h + i - max(h, i)]
    #     j = W - i - 1
    #     tmp2 = kaijo[h2 + j] * gyaku[h2 + j] * gyaku[h2 + j - max(h2, j)]
    #     ans = (ans + tmp1 * tmp2) % p
    # print(ans)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

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

res1 = math.factorial(H+W-2)//(math.factorial(H-1)*math.factorial(W-1))
res1 = res1 % (10**9 + 7)

res2 = 0

for i in range(B):
    temp1 = math.factorial(H-A-1+i)//(math.factorial(H-A-1)*math.factorial(i))
    temp1 = temp1 % (10**9 + 7)
    if A == 1:
        temp2 = 1
    else:
        temp2 = math.factorial(W+A-i-2)//(math.factorial(A-1)*math.factorial(W-i-1))
        temp2 = temp2 % (10**9 + 7)
    res2 += temp1 * temp2
    res2 = res2 % (10**9 + 7)

res = res1 - res2
res = res % (10**9 + 7)

print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC042D - いろはちゃんとマス目 / Iroha and a Grid (ARC058D)
def main():
    H, W, A, B = tuple(map(int, input().split()))
    a = H - A + 1
    MOD = 10 ** 9 + 7
    prev, cur = [0] * (W + 1), [0] * (W + 1)
    cur[0] = 1
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if i >= a and j <= B:
                continue
            cur[j] = (prev[j] + cur[j - 1]) % MOD
        if i != H:
            prev, cur = cur, [0] * (W + 1)
    print(cur[-1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

mod = 10**9 + 7
inv = mod - 2
maxn = high + width - 2
fact = [0] * (maxn+1)
finv = [0] * (maxn+1)
fact[0] = fact[1] = 1
finv[0] = finv[1] = 1

# 階乗を求める
for i in range(2, maxn+1):
    fact[i] = (fact[i-1] * i) % mod

# 階乗の逆元を求める
for i in range(2, maxn+1):
    finv[i] = powmod(fact[i], inv, mod)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(H: int, W: int, A: int, B: int):
    #H, W = W, H
    #A, B = B, A
    def comb(n, k):
        k = min(k, n - k)
        if n == 0:
            return 0
        if k == 0:
            return 1
        ret = 1
        for i in range(1, k + 1):
            ret *= (n - i + 1)
            ret //= i
        return ret

    first = [1] * (H - A)
    for i in range(1, H - A):
        first[i] = first[i - 1] * (B + i - 1)
        first[i] = first[i] // i

    second = [1] * (H - A)
    nn = A + W - B - 1
    kk = nn - (W - B - 1)
    second[0] = comb(nn, kk)
    for i in range(1, H - A):
        second[i] = second[i - 1] * (nn + i)
        second[i] = second[i] // (kk + i)

    ret = 0
    for i in range(H - A):
        ret += first[i] * second[H - A - i - 1]
        ret %= MOD
    print(ret)
    return


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())
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):return inv_n(n_func(n-r,mod),mod)*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):return inv_n(n_func(n-r,mod)*n_func(r,mod)%mod,mod)*n_func(n,mod)%mod

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

Submission status: Time Limit Exceeded

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

posA_w = b
posA_h = h - a
posB_w = w - b
posB_h = h

pa = [1] * h
pb = [1] * h
result = 0

for i in range(1, max(posA_w, posB_w)):
    for j in range(1, h):
        if i < posA_w:
            pa[j] = pa[j - 1] + pa[j]

        if i < posB_w:
            pb[j] = pb[j - 1] + pb[j]

for i in range(posA_h):
    result = (result + pa[i] * pb[posB_h - i - 1]) % 1000000007

print(str(result))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

#O(N)
first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) // i)
    first.append(tmp)

# print (first)

#O(N)
second = []
for i in range(0, H):
    if i == 0:
        tmp = 1
        second.append(tmp)
        continue
    tmp = (tmp * ((W - B) + i - 1) // i)
    second.append(tmp)

# print (second)

#O(N)
ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - 1 -i]) % MOD

print (ans)
#total O(3 * N) --> O(N)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7
first = []
for i in range(0, H - A):
    if i == 0:
        tmp = 1
        first.append(tmp)
        continue
    tmp = (tmp * (B + i - 1) // i)
    first.append(tmp)

# print (first)

second = []
for i in range(H - A):
    if i == 0:
        tmp = (math.factorial(A + (W - B - 1)) // (math.factorial(A) * math.factorial(W - B - 1)))
        second.append(tmp)
        continue
    tmp = ((tmp * (A + (W - B - 1) + i)) // (A + i))
    second.append(tmp)

# print (second)

ans = 0
for i in range(H - A):
    ans = (ans + first[i] * second[H - A - 1 -i]) % MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from math import *

p = 1000000007

def make_ft(max):
    ft = [0] * (max+1)
    x = 1
    ft[0] = 1
    # ft[i] == i!
    for i in range(1, max+1):
        x *= i
        x %= p
        ft[i] = x
    return ft

# i!^-1 == i!^(p-2) (mod p)
def make_ift(max, ft):
    ift = [0] * (max+1)
    ift[0] = 1
    for i in range(1, max+1):
        invf = 1
        x = ft[i]
        for j in range(ceil(log2(p-2))):
            # x == i!^2^j
            if ((p - 2) >> j) & 1:
                invf *= x
                invf %= p
            x *= x
            x %= p
        ift[i] = invf
    return ift

def combination(a, b, ft, ift):
    res = ft[a] * ift[b] * ift[a-b]
    res %= p
    return res

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

    ft = make_ft(H+W)
    ift = make_ift(H+W, ft)
    ans = 0
    for i in range(H-A):
        ans += combination(B+i-1, i, ft, ift) * combination(W-B+H-i-2, H-i-1, ft, ift)
        ans %= p

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import *

p = 1000000007
ft = []
ift = []

def make_ft(max):
    x = 1
    ft.append(x)
    # ft[i] == i!
    for i in range(1, max+1):
        x *= i
        x %= p
        ft.append(x)
    return

# i!^-1 == i!^(p+2) (mod p)
def make_ift(max):
    ift.append(1)
    for i in range(1, max+1):
        invf = 1
        x = ft[i]
        for j in range(ceil(log2(p-2))):
            # x == i!^2^j
            if ((p - 2) >> j) & 1:
                invf *= x
                invf %= p
            x *= x
            x %= p
        ift.append(invf)
    return

def combination(a, b):
    res = ft[a] * ift[b] * ift[a-b]
    res %= p
    return res

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

    make_ft(H+W)
    make_ift(H+W)
    ans = 0
    for i in range(H-A):
        ans += combination(B+i-1, i) * combination(W-B+H-i-2, H-i-1)
        ans %= p

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

@lru_cache(maxsize=200000)
def func(i, j) :
    if j == 0 :
        return 1
    else :
        return func(i, j-1)*(i+j)//j
ha_w = [func(h-a-1, i)%(10**9+7) for i in range(w)]
a_wb = [func(a-1, i)%(10**9+7) for i in range(w-b)]
ans = sum([ha_w[-1-i]*a_wb[i] for i in range(w-b)])%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
def p(x,y):
  if x==0 or y==0: a=0
  elif x==1 or y==1: a=1
  else: a=math.factorial(x+y-2)//math.factorial(x-1)//math.factorial(y-1)
  return a
n=0
for i in range(h-a):
  n+=(p(i+1,b))%((10**9)+7)*(p(h-i,w-b))%((10**9)+7)
n%=(10**9)+7
print(int(n))

Submission status: Time Limit Exceeded

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
def p(x,y):
  if x==0 or y==0: a=0
  elif x==1 or y==1: a=1
  else: a=math.factorial(x+y-2)//math.factorial(x-1)//math.factorial(y-1)
  return a
n=0
for i in range(h-a):
  n+=(p(i+1,b)*p(h-i,w-b))%((10**9)+7)
n%=(10**9)+7
print(int(n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

dx = [1, 0]
dy = [0, 1]


def dfs(nowx, nowy):
    if nowx == w and nowy == h:
        return 1

    if nowx > w or nowy > h or (1 <= nowx <= b and (h - a + 1) <= nowy <= h):
        return 0

    count = 0
    for i in range(2):
        count += dfs(nowx + dx[i], nowy + dy[i])
    return count


print(dfs(1, 1))

Submission status: Time Limit Exceeded

Solution code:
[h,w,a,b]=[int(_) for _ in input().split()]
import math
def p(x,y):
  if x==0 or y==0: a=0
  elif x==1 or y==1: a=1
  else: a=math.factorial(x+y-2)//math.factorial(x-1)//math.factorial(y-1)
  return a
n=0
for i in range(h-a):
  n+=p(i+1,b)*p(h-i,w-b)
n%=(10**9)+7
print(int(n))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        child %= mod
        mom *= n
        mom %= mod
        m -= 1
        n -= 1
    return (child*modpow(mom,mod-2))%mod

def modpow(m,n):
    if n == 0:
        return 1
    if n % 2:
        return ((modpow(m,n//2)**2)*m)%mod
    else:
        return (modpow(m,n//2)**2)%mod

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

ans = 0
x = 1
while x <= H - A:
    ans += combi(x+B-2,min(x,B)-1)*combi(H-x+W-B-1,min(H-x+1,W-B)-1)
    ans %= mod
    x += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        mom *= n
        m -= 1
        n -= 1
    return child//mom

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

mod = 10**9+7
ans = 0
x = 1
while x <= H - A:
    ans += combi(x+B-2,min(x,B)-1)*combi(H-x+W-B-1,min(H-x+1,W-B)-1)
    ans %= mod
    x += 1

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
n = 2 * 10**5
def mod_pow(x, n):
    ans = 1
    while(n != 0):
        if n & 1:
            ans = ans * x % MOD
        x = x * x % MOD
        n = n >> 1
    return ans

fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * mod_pow(i, MOD-2) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


def f(h, w):

    return math.factorial(h+w-2) // (math.factorial(h-1) * math.factorial(w-1))

answer = 0
for i in range(B+1, W+1):
    answer += f(H-A, i) * f(A, W-i+1)
    answer %= MOD

print(int(answer))

Submission status: Time Limit Exceeded

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