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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

fac = [-1] * (2 * 10**6+1)
inv = [-1] * (2 * 10**6+1)
finv = [-1] * (2 * 10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i] * (mod // i) % mod
        finv[i] = finv[i-1] * inv[i] % mod

def NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

initNCMMod(2 * 10**6 + 1)
def main():
    H, W, A, B = LI()
    cnt = 0
    for i in range(H-A):
        way = NCMMod(B + i - 1, i) * NCMMod(W + H - B - i - 2, W - 1 - B)
        way %= mod
        cnt += way
        cnt %= mod
    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

def modpow(base, pow, mod):
  res = 1
  while pow > 0:
    if pow & 1:
      res = res * base % mod
    base = base**2 % mod
    pow >>= 1
  return res

def modmul(a, b, mod):
  return a*b % mod

def solve(h,w,a,b):
  fact = [1]
  fact_inv = [1]
  for i in range(1, h+w):
    fact.append(fact[-1]*i % MOD)
    fact_inv.append(modpow(fact[-1], MOD-2, MOD))

  ans = 0
  for col_idx in range(b, w):
    before_checkpoint = modmul(modmul(fact[h-a-1+col_idx], fact_inv[h-a-1], MOD), fact_inv[col_idx], MOD)
    from_checkpoint = modmul(modmul(fact[(a-1) + (w-col_idx-1)], fact_inv[w-col_idx-1], MOD), fact_inv[a-1], MOD)
    ans = (ans + modmul(before_checkpoint, from_checkpoint, MOD)) % MOD

  return ans

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())
b=[[0 for j in range(W)] for i in range(H)]
MOD=1000000007
b[0][0]=1
for j in range(H):
	for i in range(W):
		if j+1<H and (j+1<H-A or i>=B):
			b[j+1][i]+=b[j][i]
			b[j+1][i]%=MOD
		if i+1<W and (j<H-A or i+1>=B):
			b[j][i+1]+=b[j][i]
			b[j][i+1]%=MOD

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

"""
kari1 = '100000 100000 99990 99990'
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0]) #縦Hマス
W = int(in1[1]) #横Wマス
A = int(in1[2]) #下からAマス
B = int(in1[3]) #左からBマス

allCNT = 0
for idx1 in range(W - B):
    beforeCNT = combinations_count((H - A - 1) + B + idx1, (H - A - 1))
    afterCNT  = combinations_count((A - 1) + (W - B - 1 - idx1), (A - 1))
    allCNT    = allCNT + (beforeCNT * afterCNT)

allCNT = allCNT % ((10 ** 9) + 7)

print(allCNT)

Submission status: Time Limit Exceeded

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

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

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

Submission status: Time Limit Exceeded

Solution code:
def f(x):
    if x==0:
        return 1
    else:
        fac=1
        for i in range(1,x+1):
            fac*=i
        return fac
def c(x,y):
    return f(x+y)//(f(x)*f(y))
h,w,a,b=map(int,input().split())
ans=0
ans+=c((h-a-1),(b))*c((a),(w-b-1))
for i in range(h-a-1):
    ans+=c(i,b)*c(h-i-1,w-b-2)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

    def __str__(self):
        return str(self.num)

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


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

power = [ModInt(1, mod)]
inv = [ModInt(1, mod).inverse()]


def comb(n, r):
    return power[n] * inv[r] * inv[n-r]


for i in range(1, h + w - 1):
    power.append(power[-1] * ModInt(i, mod))
    inv.append(power[-1].inverse())

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
H,W,A,B=map(int,input().split())
p=0
for i in range(B+1,W+1):
    p+=comb(H-A+i-2,i-1,exact=True)*comb(W-i+A-1,A-1,exact=True)
k=p%1000000007
print(k)

Submission status: Time Limit Exceeded

Solution code:
# D - いろはちゃんとマス目
def combmod(n,k,mod):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n-i) % mod
        b = b * (i+1) % mod
    return a * pow(b, mod-2, mod) % mod

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

mod=10**9+7
ans=0
for i in range(b,w):
    ans+=combmod(i+h-1-a,i,mod)*combmod(w-1-i+a-1,a-1,mod)
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions 
H,W,A,B=map(int,input().split())
def C(n,m):
    if n*m==0:
        C =1
    else:
        bunbo=[0]*min(m,n)
        bunsi=[0]*min(m,n)
        for k in range(min(m,n)):
            bunbo[k]=min(m,n)-k
            bunsi[k]=n+m-k
        for k in range(min(m,n)):
            for j in range(min(n,m)):
                gcd=fractions.gcd(bunbo[k],bunsi[j])
                bunbo[k]=bunbo[k]//gcd
                bunsi[j]=bunsi[j]//gcd
        x=1
        y=1
        for k in range(min(n,m)):
            x=x*bunsi[k]
            y=y*bunbo[k]
        C=x//y
    return C
Total = C(H-1,W-1)
dame = 0
for k in range(B):
    dame += C(k,H-A-1)*C(W-1-k,A-1)
answer = (Total-dame)%(10**9+7)
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
H,W,A,B=map(int,input().split())
def bikkuri(n,m):
    x=n
    if m>1:
        for k in range(1,m):
            x=x*(n-k)
    return x
def C(n,m):
    if m==0:
        C=1
    else:
        C=bikkuri(n+m,m)//bikkuri(m,m)
    return int(C)
Total = C(H-1,W-1)
dame = 0
for k in range(B):
    dame += C(k,H-A-1)*C(W-1-k,A-1)
answer = (Total-dame)%(10**9+7)
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

class Combination:
    def __init__(self,max_n):
        self.max_n=0
        self.fact=[Fp(1)]
        self.ifact=[Fp(1)]
        self.make_fact_list(max_n)
    def C(self,n,k):return self.fact[n]*self.ifact[k]*self.ifact[n-k] if 0<=k<=n else 0
    def H(self,n,k):return self.C(n+k-1,k) if n or k else 1
    def P(self,n,k):return self.fact[n]*self.ifact[n-k] if 0<=k<=n else 0
    def make_fact_list(self,max_n):
        if max_n<=self.max_n: return
        self.fact+=[Fp(0)]*(max_n-self.max_n)
        self.ifact+=[Fp(0)]*(max_n-self.max_n)
        for i in range(self.max_n+1,max_n+1):
            self.fact[i]=self.fact[i-1]*i
            self.ifact[i]=self.ifact[i-1]//i
        self.max_n=max_n

def main():
    H, W, A, B = map(int, input().split())
    C = Combination(H+W)
    ans = C.C(H+W-2, H-1)
    for b in range(B):
        ans -= C.C(H-A-1+b, b) * C.C(A-1+W-b-1, A-1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,A,B = map(int,input().split())
mod = 10**9+7
def comb(a,b,p):
    if a<0 or b<0 or a<b: return 0
    if a==0 or b==0: return 1
    fa = 1
    fb = 1
    fab = 1
    for i in range(1,a+1):
        fa = (fa*i)%p
    for i in range(1,b+1):
        fb = (fb*i)%p
    for i in range(1,a-b+1):
        fab = (fab*i)%p
    return (fa*power2(fb,p-2,p)*power2(fab,p-2,p))%p
def power2(a,b,p):
    if b == 0:
        return 1
    if b%2 == 0:
        d = power2(a,b//2,p)
        return (d*d)%p
    return (a*power2(a,b-1,p))%p
ans = 0
for w in range(B,W):
    ans = (ans+ (comb(H-A+w-1,w,mod)*comb(A+W-w-2,A-1,mod))%mod)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 回答の最大値（固定数）
T = 10**9 + 7

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

# 計算済みの経路
route = {(0, 0):1}

# 計算対象の経路
stack = [(H-1, W-1)]

# 計算対処の経路が空になるまで繰り返し
while stack != []:
    # 現在のマス
    curr = stack.pop()
    
    # 一つ手前のマス（上）。
    if curr[0]-1 >= 0:
        upper = (curr[0]-1, curr[1])
    else:
        upper = None
    
    # 一つ手前のマス（左）。下からA個、左からB個以内に引っかかる可能性がある。
    if curr[1]-1 >= 0 and (curr[0] < H-A or curr[1]-1 >= B):
        left = (curr[0], curr[1]-1)
    else:
        left = None
    
    # 経路の計算
    if upper != None and left != None:
        # 一つ手前のマスがどちらも有効なマスの場合
        
        if upper in route and left in route:
            # 一つ手前のマスがどちらも計算済みなら現在のマスを計算可能
            route[curr] = (route[upper]+route[left])%T
        else:
            # どちらかのマスが未計算なら現在のマスの計算は一旦保留
            stack.append(curr)
            
            # 未計算のマスをスタックに追加
            if upper not in route:
                stack.append(upper)
            if left not in route:
                stack.append(left)
    
    elif upper != None:
        # 一つ手前のマス（上）のみ有効なマスの場合
        
        if upper in route:
            # 一つ手前のマス（上）が計算済みなら現在のマスを計算可能
            route[curr] = route[upper]
        else:
            # 一つ手前のマス（上）が未計算なら現在のマスの計算は一旦保留
            stack.append(curr)
            
            # 未計算のマスをスタックに追加
            stack.append(upper)
    
    elif left != None:
        # 一つ手前のマス（左）のみ有効なマスの場合
        
        if left in route:
            # 一つ手前のマス（左）が計算済みなら現在のマスを計算可能
            route[curr] = route[left]
        else:
            # 一つ手前のマス（左）が未計算なら現在のマスの計算は一旦保留
            stack.append(curr)
            
            # 未計算のマスをスタックに追加
            stack.append(left)
    
    else:
        # 一つ手前のマスがどちらも有効なマスでない場合
        # 今回のプログラムではこのケースは存在しない。エラーメッセージを出し手抜ける。
        print('invalid route(' + str(curr[0]) + ', ' + str(curr[1]) + ')')
        sys.exit(1)

# 右下の経路が計算されているはずなので表示
if (H-1, W-1) in route:
    print(route[(H-1, W-1)])
else:
    print('Error')

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
if a <= h // 2:
    ans = 0
    for i in range(1, h - a + 1):
        ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
        if ans >= MOD:
            ans -= MOD
    print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
ans = 0
for i in range(1, h - a + 1):
    ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
    if ans >= MOD:
        ans -= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def modinv(x):
    ret = 1
    m = MOD - 2
    for i in range(0, 32):
        if m & (1 << i):
            ret *= x
            ret %= MOD
        x *= x
        x %= MOD
    return ret


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
ans = 0
for i in range(1, h - a + 1):
    ans += calc(i, b) * calc(h + 1 - i, w - b) % MOD
    if ans >= MOD:
        ans -= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 10**9+7


def modinv(x):
    ret = 1
    m = MOD - 2
    '''
    while m:
        if m & 1:
            ret = ret * x % MOD
        x = x * x % MOD
        m >>= 1
    '''
    for i in range(0, 32):
        if m & (1 << i):
            ret *= x
            ret %= MOD
        x *= x
        x %= MOD
    return ret


fact = [1] * 200100
for i in range(1, 200100):
    fact[i] = fact[i-1] * i % MOD


def calc(h, w):
    h -= 1
    w -= 1
    return (fact[h+w]*modinv(fact[h]) % MOD)*modinv(fact[w]) % MOD


h, w, a, b = map(int, input().split())
ans = 0
for i in range(1, h - a + 1):
    ans += calc(i, b) * calc(h + 1 - i, w - b)
    ans %= MOD
    # print(ans)
print(ans)
'''
print(modinv(2))
print(bin(MOD-2))
#print(2**(MOD-2) % MOD)
'''

Submission status: Time Limit Exceeded

Solution code:
import math

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

if h - a > w - b:
  hh = h
  h = w
  w = hh
  del hh
  aa = a
  a = b
  b = aa
  del aa

x = h - a + b - 1
y = w + a - b - 1
z = h - 1

d = math.factorial(y) // (math.factorial(y - z) * math.factorial(z))
c = d

for t in range(0, h - a - 1):
    d = ((d * (x - t) * (z - t)) // ((t + 1) * (y - z + t + 1)))
    c += d%(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

c=0

for k in range(h - a ):
    c += (combination(b + k - 1, k) * combination(h + w - b - k - 2, w - b - 1))%(10**9+7)
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

c=0

for k in range(h - a ):
    c += combination(b + k - 1, k) * combination(h + w - b - k - 2, w - b - 1)
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from array import *

h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = 2*10**5

def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
f = array('q', f)
ivf = [0] * MAX
ivf = array('q', ivf)
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))

Submission status: Time Limit Exceeded

Solution code:
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = 3*10**5


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
ivf = [0] * MAX
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))

Submission status: Time Limit Exceeded

Solution code:
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = 2*10**5


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
ivf = [0] * MAX
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

h, w, a, b = map(int, input().split(' '))
# MAX = max(h, w)
MOD = 10**9 + 7
MAX = 10**6


def modpow(a, b):
    res = 1
    while b:
        if (b & 1):
            res = (res * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return res


def nCr(n, r):
    if r == 0 or n == r:
        return 1
    return (((f[n] * ivf[n-r]) % MOD) * ivf[r]) % MOD


f = [1] * MAX
ivf = [0] * MAX
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    ivf[i] = modpow(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (nCr(x1 + y1, x1) * nCr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD
print(int(r))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
MAX = 10**6 + 5


def mod(a, b):
    r = 1
    while b:
        if b & 1:
            r = (r * a) % MOD
        a = (a * a) % MOD
        b >>= 1
    return r


f = [0]*MAX
invf = [0]*MAX


def ncr(n, r):
    if r == 0 or r == n:
        return 1
    return (((f[n] * invf[n-r]) % MOD) * invf[r]) % MOD


f[0] = 1
for i in range(1, MAX):
    f[i] = (f[i-1] * i) % MOD
    invf[i] = mod(f[i], MOD-2)
r = 0
for i in range(b, w):
    y1 = h - a - 1
    x1 = i
    y2 = a - 1
    x2 = w - i - 1
    p = (ncr(x1 + y1, x1) * ncr(x2 + y2, x2)) % MOD
    r = (r + p) % MOD

print(r)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
H,W,A,B=map(int,input().split())
n=[[0 for j in range(W)] for i in range(H)]
n[0][0]=1
for j in range(1,W):
    n[0][j]=n[0][j-1]
for i in range(1,H-A):
    n[i][0]=n[i-1][0]
    for j in range(1,W):
        n[i][j]=(n[i-1][j]+n[i][j-1])%mod
for i in range(H-A,H):    
    n[i][B]=n[i-1][B]
    for j in range(B+1,W):
        n[i][j]=(n[i-1][j]+n[i][j-1])%mod

print(n[-1][-1])

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7
flist = [1] * (h+w+1)
for i in range(1,h+w):
    flist[i] = (flist[i-1] * i)

def cmb(n,r):
    return flist[n]//(flist[r]*flist[n-r])

for x in range(b,w):
    c = x + (h - a - 1)
    d = (w - x - 1) + (a - 1)
    e = cmb(c, x) * cmb(d, a - 1)
    ans = (ans+e)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

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

#全体
total = cmb(H+W-2,W-1)

#侵入不可

forbidden = sum(cmb(H-A+i-2,i-1) * cmb(W-i+A-1,A-1) for i in range(1,B+1))

answer = int(total - forbidden)
print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

nums = input().split()
H = int(nums[0])
W = int(nums[1])
A = int(nums[2])
B = int(nums[3])
mod = 1000000007

#全体
total = cmb(H+W-2,W-1)

#侵入不可
K = 1
forbidden = 0
while K < B + 1:
    x1 = cmb(H-A+K-2,K-1)
    x2 = cmb(W-K+A-1,A-1)

    x = x1 * x2
    forbidden += x
    x = 0
    x1 = 0
    x2 = 0
    K += 1

answer = int(total - forbidden)
print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p
h,w,a,b=map(int,input().split())
mod=10**9+7
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i,mod)*comb(w-b+a-1,a+i,mod)
print(t%mod)

Submission status: Time Limit Exceeded

Solution code:
base = 10**9 + 7

def comb(x, y):#xCy = [x-1]C[y-1] * n / k
  res = 1
  for i in range(x):
    res = res * (x-i)
  for i in range(y):
    res = res // (i+1)
  for i in range(x-y):
    res = res // (i+1)
  return res % base

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

res = 0
for i in range(W-B):
  res += comb(H-A-1 + W-i-1, W-i-1)*comb(A-1+i,i)
  res %= base
print(res)

Submission status: Time Limit Exceeded

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

f1 = [1 for i in range(W)]
f2 = [0 for i in range(W)]

for i in range(H-1): #f1 -> #f2
  for j in range(W):
    if i > H-2-A and j<B:
      f2[j] = 0
    elif j == 0:
      f2[0] = f1[0]
    else:
      f2[j] = f1[j] + f2[j-1]
  for j in range(W):
    f1[j] = f2[j]%base
  #print(f1)
print(f1[W-1])

Submission status: Time Limit Exceeded

Solution code:
def examD():
    from operator import mul
    from functools import reduce
    def comb2(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

    H, W, A, B =LI()
    k = W-B
    ans = int(0)
    C1 = [0]*k; C2 = [0]*k
    for i in range(k):
        C1[i] = comb2(H-A+B+i-1,H-A-1)%mod
        C2[i] = comb2(A+W-(B+i)-2,A-1)%mod
        ans = (ans+C1[i]*C2[i])%mod
    print(ans)
#    print(C1)
#    print(C2)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Time Limit Exceeded

Solution code:
#D問題
import math
H,W,A,B = map(int,input().split())
mod = 10**9 + 7

M = H+W-1
fact = [1 for i in range(M)]
for i in range(M):
    if i == 0:
        pass
    else:
        fact[i] = (fact[i-1]*i)%mod
        
refact = [1 for i in range(M)]
m = mod-2
b = bin(m)
b = b.lstrip("0b")
b = b[::-1]
m2 = len(b)
for i in range(M):    
    flog = [0 for j in range(m2)]
    for j in range(m2):
        if j == 0:
            flog[0] = fact[i]
        else:
            flog[j] = (flog[j-1]**2)%mod
    #print(flog)
    for j in range(m2):
        if b[j] == "1":
            refact[i]*=flog[j]
            refact[i]%=mod
            
row = B
wide = W-B
ans = 0
for i in range(wide):
    row = B+i
    C1 = (fact[H-A+row-1]*refact[H-A-1]*refact[row])%mod
    C2 = (fact[W+A-row-2]*refact[W-row-1]*refact[A-1])%mod
    #print(C1,C2)
    ans+=C1*C2
    ans%=mod

#print(fact)
#print(refact)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
def power(a,x):
    if x==0:
        return 1
    if x%2==0:
        return (power((a**2)%p,x//2))%p
    else:
        return (a*power((a**2)%p,(x-1)//2))%p
H,W,A,B = map(int,input().split())
tot = 0
for k in range(W-B):
    a1 = 1
    for i in range(H-A-k,H-A+B):
        a1 = (a1*i)%p
    b1 = 1
    for i in range(W-B-k,A+W-B):
        b1 = (b1*i)%p
    a2 = 1
    for i in range(2,A+k+1):
        a2 = (a2*i)%p
    a2 = pow(a2,p-2)
    b2 = 1
    for i in range(2,B+k+1):
        b2 = (b2*i)%p
    b2 = pow(b2,p-2)
    tot = (tot+a1*a2*b1*b2)%p
print(tot)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
def power(a,x):
    if x==0:
        return 1
    if x%2==0:
        return (power(a**2,x//2))%p
    else:
        return (a*power(a**2,(x-1)//2))%p
H,W,A,B = map(int,input().split())
tot = 0
for k in range(W-B):
    a1 = 1
    for i in range(H-A-k,H-A+B):
        a1 = (a1*i)%p
    b1 = 1
    for i in range(W-B-k,A+W-B):
        b1 = (b1*i)%p
    a2 = 1
    for i in range(2,A+k+1):
        a2 = (a2*i)%p
    a2 = pow(a2,p-2)
    b2 = 1
    for i in range(2,B+k+1):
        b2 = (b2*i)%p
    b2 = pow(b2,p-2)
    tot = (tot+a1*a2*b1*b2)%p
print(tot)

Submission status: Time Limit Exceeded

Solution code:

import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]

for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
def c(a,b):
    return M[a+b-2]*power(M[a-1],e-2)*power(M[b-1],e-2)%e

T = 0
for i in range(B+1,W+1):
    P = c(H-A,i)
    Q = c(A,W-i+1)
    T = (T + P*Q)
print(T%e)

Submission status: Time Limit Exceeded

Solution code:
import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
N = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
    b = power(M[i],e-2)
    N.append(b)
def c(a,b):
    return M[a+b-2]*N[a-1]*N[b-1]%e

T = 0
for i in range(B+1,W+1):
    P = c(H-A,i)
    Q = c(A,W-i+1)
    T = (T + P*Q)
print(T%e)

Submission status: Time Limit Exceeded

Solution code:
import math
H, W, A, B = map(int,input().split())
e = 10**9 + 7
def power(a,b):
    if b == 0:
        return 1
    elif b == 1:
        return a % e
    elif b%2 == 0:
        return power(a,b//2)**2 % e
    else:
        return power(a,b//2)**2*a % e
    
M = [1]
for i in range(1,H+W):
    a = M[i-1]*i%e
    M.append(a)
N = []
for i in range(H+W):
    b = power(M[i],e-2)
    N.append(b)
def c(a,b):
    return M[a+b-2]*N[a-1]*N[b-1]%e

T = 0
for i in range(B+1,W+1):
    P = c(H-A,i)
    Q = c(A,W-i+1)
    T = (T + P*Q)
print(T%e)

Submission status: Time Limit Exceeded

Solution code:
import math
H, W, A, B = map(int,input().split())
def f(a,b):
    p = math.factorial(a+b-2)
    q = math.factorial(a-1)
    r = math.factorial(b-1)
    S = p // (q*r)
    return S
T = 0
for i in range(1,B+1):
    P = f(H-A,i)
    Q = f(A,W-i+1)
    T = T + P*Q
R = f(H,W) - T
ans = R % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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


def combination(num1, num2):
    return math.factorial(num1 + num2) // (math.factorial(num1) * math.factorial(num2))


all = combination(h - 1, w - 1)
for i in range(b):
    comb_i = combination(h - a - 1, i)
    to = combination(a - 1, w - 1 - i)
    all -= comb_i * to
print(all % (10 ** 9 + 7))