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: Runtime Error

Solution code:
import math

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

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

def way_num(x, y):
  return comb(x+y-2, x-1)

all_num=way_num(h, w)

no_num=0

for i in range(b):
  
  to_here=way_num(h-a+1, i+1)
  from_here=way_num(a, w-i)
  
  if i>0:
    overlap=way_num(h-a+1, i)*from_here
  else:
    overlap=0
    
  no_num+=to_here*from_here-overlap
  
num=all_num-no_num

res=num%(10**9+7)

print(res)

Submission status: Runtime Error

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

xList = list(range(w-b))
Py = h-a-1
mod = 10**9+7

def combination(x, y):
    c = factorial(x)/(factorial(y)*factorial(x-y))
    return c

def factorial(x):
    f = 1
    for i in range(1,x+1):
        f *= i
    return f

ans = 0
for x in xList:
    Px = b+x
    Gx = a+w-1-b-x
    if x == 0:
        buf = combination(Px+Py,Px)*combination(Gx,a)%mod
    else:
        buf = (combination(Px+Py,Px)-combination(Px+Py-1, Px-1))*combination(Gx,a)%mod
    # print(Px,Py,Gx,a)
    ans += buf

print(ans)

Submission status: Runtime Error

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

xList = list(range(w-b))
Py = h-a-1

def combination(x, y):
    c = factorial(x)/(factorial(y)*factorial(x-y))
    return c

def factorial(x):
    f = 1
    for i in range(1,x+1):
        f *= i
    return f

ans = 0
for x in xList:
    Px = b+x
    Gx = a+w-1-b-x
    if x == 0:
        buf = combination(Px+Py,Px)*combination(Gx,a)
    else:
        buf = (combination(Px+Py,Px)-combination(Px+Py-1, Px-1))*combination(Gx,a)
    # print(Px,Py,Gx,a)
    ans += buf

print(ans%1000000007)

Submission status: Runtime Error

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
S=sum(comb(a+k,a)*(comb(b-i,c)%(10**+7) for k in range(M))
print(S%(10**9+7))

Submission status: Runtime Error

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
S=sum(comb(a+k,a)*(comb(b-i,c) for k in range(M))
print(S%(10**9+7))

Submission status: Runtime Error

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
S=sum(comb(a+k,a)*comb(b-i,c) for k in range(M))
print(S)

Submission status: Runtime Error

Solution code:
def fac(x):
  y=1
  for i in range(x):
    y*=(i+1)
  return(y)

def combi(i,j):
  x=fac(i+j)/(fac(i)*fac(j))
  return(int(x))

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

Submission status: Runtime Error

Solution code:
def fac(x):
  y=1
  for i in range(x):
    y*=(i+1)
  return(y)

def combi(i,j):
  x=fac(i+j)/(fac(i)*fac(j))
  return(int(x))

h,w,a,b=map(int,input().split())
all=combi(h-1,w-1)
z=[[0 for i in range(a)] for j in range(b)]
exc=0
for i in range(b):
  for j in range(a):
    if i==0:
      z[i][j]=1
    elif j==0:
      z[i][j]=combi(h-a+j-1,i)+z[i-1][j]
    else:
      z[i][j]=z[i][j-1]+z[i-1][j]
for i in range(a):
  exc+=z[b-1][i]*combi(a-i-1,w-b-1)
ans=all-exc
print(int(ans%(10**9+7)))

Submission status: Runtime Error

Solution code:
def fac(x):
  y=1
  for i in range(x):
    y*=(i+1)
  return(y)

def combi(i,j):
  x=fac(i+j)/(fac(i)*fac(j))
  return(x)

h,w,a,b=map(int,input().split())
all=combi(h-1,w-1)
exc=0
for i in range(a):
  exc+=combi(a-1-i,b-1)*combi(i,w-b-1)
ans=all-exc
print(int(ans%(10^9+7)))

Submission status: Runtime Error

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, exact=True)
    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: Runtime Error

Solution code:
H,W,A,B = map(int, input().split())
a = H-A
res = 0
for i in range(1,B+1):
    ex1 = comba(a-1+i-1,i-1)
    print("ex1="+str(ex1))
    ex2 = comba(A-1+W-i,W-i)
    print("ex2="+str(ex2))
    exres = ex1 *ex2
    res = res + exres

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

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<tuple>
#include<vector>
#include<cstdlib>
#include<cstdint>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip> 
#include<ctime>
#include<climits>
#include<random>
#include<queue>


using namespace std;

template <class T> using V = vector<T>;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

using ll = long long;
using db = long double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using graph = V<V<int>>;
using pq = priority_queue<ll>;



#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define pb(a) push_back(a);
#define ALL(a)  (a).begin(),(a).end()




ll Sum(ll n) {
ll m=0;
  while(n){
    m+=n%10;
    n/=10;
  }
  return m;
}



const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


#define comuse Comuse()

ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll perm(int n,int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] % MOD) % MOD;
}

ll modpow(ll a,ll n,ll mod){
  ll ans=1;
  while(n>0){
    if(n&1){
      ans=ans*a%mod;
    }

    a=a*a%mod;
    
    n>>=1;
  }

  return ans;
}

ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

ll modcombi(int n,int k,int mod){
  ll ans=1;
  for(ll i=n;i>n-k;i--){
    ans*=i;
    ans%=mod;
  }
  for(ll i=1;i<=k;i++){
    ans*=modinv(i,mod);
    ans%=mod;
  }

  return ans;
}

ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}


vll div(ll n){
  vll ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      ret.push_back(i);
      if(i*i!=n){
        ret.push_back(n/i);
      }
    }
  }
  SORT(ret);
  return (ret);
}

vector<bool> isprime(MAX+100,true);

void primeuse(){
  isprime[0]=false;
  isprime[1]=false;
  for(int i=2;i<MAX+50;i++){
    int up=sqrt(i)+1;
    for(int j=2;j<up;j++){
      if(i%j==0){
        isprime[i]=false;
      }
    }
  }
}



void Solve();


const int MAX_N = 131072;
//segment tree 
int NN;
int seg[MAX_N*2-1];
void seguse(){
  for(int i=0;i<2*NN-1;i++){
    seg[i]=INT_MAX;
  }
}



signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}



/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
//segtreeの葉の先頭の添え字はN-1
void Solve(){
  //ll N=262144;
  //vll segtree(2*N-1);
  ll n;
    cin>>n;
  vll A(n);
  FOR(i,0,n){
    cin>>A[i];
  }
  REV(A);
  ll ans=0;
  ll now=1;
  FOR(i,0,n){
    ans+=now*A[i];
    if(A[i]<10){
      now*=10;
    }
    else if(A[i]<100){
      now*=100;
    }
    else if(A[i]<1000){
      now*=1000;
    }
    else if(A[i]<10000){
      now*=10000;
    }
    else{
      now*=100000;
    }
    now%=MOD;
    ans%=MOD;
  }
  cout<<ans<<"\n";
}

Submission status: Runtime Error

Solution code:
# 解説を見て解いた。解説PDFの「B≦i≦Wを満たす全てのiについて」のWはW-1の間違い。
def make_table(h, w):

    for i in range(1, h + w - 1):
        fac_table.append(fac_table[-1] * i % mod)  # i! mod 10**9+7
        inv_table.append(pow(fac_table[-1], mod - 2, mod))  # (i!)^(-1) mod 10**9+7.


def comb(n, r):
    return fac_table[n] * inv_table[n - r] * inv_table[r] % mod


def resolve():
    H, W, A, B = map(int, input().split())
    make_table(H, W)
    _sum = 0
    print(
        sum(
            [
                comb(H - A - 1 + i, i) * comb(A - 1 + W - i - 1, A - 1) % mod
                for i in range(B, W)
            ]
        )
        % mod
    )


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import math
h, w, a, b = map(int, input().split())
ans = 0
rp = [h-a-1, b]
def f(x):
  if x == 0:
    return 1
  else:
    a = 1
    for i in range(1, x+1):
      a *= i
    return a
def c(x, y):
  return f(x)/(f(y)*f(x-y))
sum = 0
while True:
  x = c(rp[0]+rp[1], rp[0]) * c((h-rp[0]-1)+(w-rp[1]-1), h-rp[0]-1)
  sum += x
  if rp[0] <= 0 or rp[1] >= w-1:
    break
  rp[0] -= 1
  rp[1] += 1
print(math.floor(sum))

Submission status: Runtime Error

Solution code:
h, w, a, b = map(int, input().split())
ans = 0
rp = [h-a-1, b]
def f(x):
  if x == 0:
    return 1
  else:
    a = 1
    for i in range(1, x+1):
      a *= i
    return a
def c(x, y):
  return f(x)/(f(y)*f(x-y))
sum = 0
while True:
  x = c(rp[0]+rp[1], rp[0]) * c((h-rp[0]-1)+(w-rp[1]-1), h-rp[0]-1)
  sum += x
  if rp[0] <= 0 or rp[1] >= w-1:
    break
  rp[0] -= 1
  rp[1] += 1
print(sum)

Submission status: Runtime Error

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

# grobalにmdを設定すること
class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 100005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

def main():
    h,w,a,b=MI()
    cc=[]
    for i in range(h-a):
        cc.append(nCr(b+i,i))
    #print(*cc)
    ans=mint(0)
    pc=0
    for i,c in enumerate(cc):
        ans+=(c-pc)*nCr(h-1-i+w-1-b,w-1-b)
        pc=c
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import math 
  
# Function to find modulo inverse of b. It returns  
# -1 when inverse doesn't  
# modInverse works for prime m 
def modInverse(b,m): 
    g = math.gcd(b, m)  
    if (g != 1): 
        # print("Inverse doesn't exist")  
        return -1
    else:  
        # If b and m are relatively prime,  
        # then modulo inverse is b^(m-2) mode m  
        return pow(b, m - 2, m) 
  
  
# Function to compute a/b under modulo m  
def modDivide(a,b,m): 
    a = a % m 
    inv = modInverse(b,m) 
    if(inv == -1): 
        print("Division not defined") 
    else: 
        return (inv*a) % m

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

DP = []
j = 1
for i in range(1,200002):
    j *= i
    j %= MOD
    DP.append(j)

# print(DP)
def factorial(i):
    if (i == 0):
        return 1
    global DP
    # print(i)
    # print(i, DP[i-1])
    # print(DP[i-1])
    return DP[i-1]

def move2(H, W, A, B):
    numPaths = 0
    h = H-A
    w = W-(W-B)+1
    a = A+1
    pttp = 0
    for b in range(w, W+1):
        # print(h, b, a, W-b+1)
        ttp = (factorial(h+b-2)*modInverse((factorial(h-1)*factorial(b-1))% MOD, MOD)) % MOD
        tpttp = ttp
        ttp -= pttp
        pttp = tpttp
        btp = (factorial(a+(W-b+1)-2)*modInverse((factorial(a-1)*factorial(W-b))% MOD, MOD)) % MOD
        # btp = factorial(a+(W-b+1)-2)//(factorial(a-1)*factorial(W-b))
        numPaths += ttp*btp
    return numPaths

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

Submission status: Runtime Error

Solution code:
from operator  import mul
from functools import reduce

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

p = 10 ** 9 + 7
N = 10 ** 5
fact    = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv     = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#kari1 = '2 3 1 1'                   #2
#kari1 = '10 7 3 4'                  #3570
#kari1 = '100000 100000 99999 99999' #1
#kari1 = '100000 100000 44444 55555' #738162020

"""
in1 = kari1.split()
"""
in1 = input().split()

H = int(in1[0])
W = int(in1[1])
A = int(in1[2])
B = int(in1[3])

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

print(allCNT)

Submission status: Runtime Error

Solution code:
from sys import stdin
from operator import itemgetter
##stdin = open("sample.txt")

H,W,A,B = [int(x) for x in stdin.readline().rstrip().split()]

def fact(a):
    if a == 0:
        return 1
    elif a == 1:
        return a
    else:
        return a * fact(a-1)

path_list = list(range(W-B))
path_list2 = list(range(0))
path_list.reverse()

for path in path_list:
    path_list2.append(fact((W-path-1)+(H-A-1))//fact(W-path-1)//fact(H-A-1))
 
H2 = A+1
W2 = W-B
path2_list = [[0] * (W2) for i in range(H2)]

h = 0
w = 0
while h < H2:
    path2_list[h][0] = path_list2[0]
    h += 1
while w < W2:
    path2_list[0][w] = path_list2[w]
    w += 1

h2 = 1
w2 = 1
ans = 0
while h2 <= H2-1 and w2 <= W2-1:
    ans = (path2_list[h2-1][w2] + path2_list[h2][w2-1])
    path2_list[h2][w2] = ans
    if w2 == W2-1:
        h2 += 1
        w2 = 1
    else:
        w2 += 1
print(path2_list[H2-1][W2-1])

Submission status: Runtime Error

Solution code:
from sys import stdin
from operator import itemgetter
#stdin = open("sample.txt")

H,W,A,B = [int(x) for x in stdin.readline().rstrip().split()]

def fact(a):
    if a == 1:
        return a
    return a * fact(a-1)

path_list = list(range(W-B))
path_list2 = list(range(0))
path_list.reverse()

for path in path_list:
    path_list2.append(fact((W-path-1)+(H-A-1))//fact(W-path-1)//fact(H-A-1))
 
H2 = A+1
W2 = W-B
path2_list = [[0] * (W2) for i in range(H2)]

h = 0
w = 0
while h < H2:
    path2_list[h][0] = path_list2[0]
    h += 1
while w < W2:
    path2_list[0][w] = path_list2[w]
    w += 1

h2 = 1
w2 = 1
ans = 0
while h2 <= H2-1 and w2 <= W2-1:
    ans = (path2_list[h2-1][w2] + path2_list[h2][w2-1])
    path2_list[h2][w2] = ans
    if w2 == W2-1:
        h2 += 1
        w2 = 1
    else:
        w2 += 1
print(path2_list[H2-1][W2-1])

Submission status: Runtime Error

Solution code:
H, W, A, B = list(map(int, input().split()))
up = [[0]*W for i in range(H-A)]
down = [[0]*(W-B) for i in range(A)]
#上側ここから
for i in range(1, W):
  up[0][i] = 1
for j in range(1, H-A):
  up[j][0] = 1
for i in range(1, H-A):
  for j in range(1, W):
    up[i][j] = up[i-1][j] + up[i][j-1]
#下側ここから
down[0][0] = up[H-(A+1)][B]
for i in range(1, W-B):
  down[0][i] = up[H-(A+1)][B+i] + down[0][i-1]
for j in range(1, A):
  down[j][0] = down[j-1][0]
   
for j in range(1, A):
  for i in range(1, W-B):
    down[i][j] = down[i-1][j] + down[i][j-1]
#print(up)
#print(down)
output = down[A-1][W-(B+1)] % (10**9+7)
print(output)

Submission status: Runtime Error

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

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

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

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

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

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

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
H, W, A, B = map(int, input().split())

r = 0
for i in range(H-A):
#    (0, 0) -> (i, B-1)
#    (i, B) -> (H-1, W-1)
    r = (r + mul(cmb(i+B-1, i), cmb(H-1-i+W-1-B, H-1-i)))%mod
print(r)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
readline = lambda:sys.stdin.readline().rstrip()

def solve(H,W,A,B):
    a = np.zeros([H,W], dtype=np.int32)
    a[:-A, 0] = 1
    a[0, 1:] = 1
    
    #[1-B)
    for y in range(1, H-A):
        a[y, 1:] += a[y-1, 1:]
        for x in range(1, W):
            a[y, x] = np.sum(a[y, x-1:x+1]) % (10**9+7)
    #[B-H)
    for y in range(H-A, H):
        a[y, B:] += a[y-1, B:]
        for x in range(B+1, W):
            a[y, x] = np.sum(a[y, x-1:x+1]) % (10**9+7)

    return a

def main():
    H, W, A, B = [int(s) for s in readline().split()]
    if H>W:
        H,W,A,B = W,H,B,A
    ans = solve(H,W,A,B)
    print(ans[H-1, W-1])
    
main()

Submission status: Runtime Error

Solution code:
import fractions
H,W,A,B=map(int,input().split())
mod =10**9+7
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)):
                if math.gcd(bunsi[j],bunbo[k])==0:
                    gcd =fractions.gcd(bunsi[j],bunbo[k])
                    bunsi[j]=bunsi[j]//gcd
                    bunbo[k]=bunbo[k]//gcd
                if bunbo[k]==1:
                    break   
        C=1
        for k in range(min(n,m)):
            C=C*bunsi[k]%mod
    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)%mod
print(answer)

Submission status: Runtime Error

Solution code:
import math 
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=math.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: Runtime Error

Solution code:
H,W,A,B=map(int,input().split())
def C(n,m):
    C=1
    for k in range(m):
        C = C*(n+m-k)/(m-k)
    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: Runtime Error

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

Submission status: Runtime Error

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

def combination(n, r) :
    num_1 = 1
    num_2 = 1
    for j in range(n-r) :
        num_1 *= (n-j)
        num_2 *= (j+1)
    num_ans = int(num_1 / num_2)
    return num_ans

for i in range(b) :
    n1 = h-a+i-1
    r1 = i
    n2 = w+a-i-2
    r2 = a-1
    x = combination(n1, r1)
    y = combination(n2, r2)
    count += x*y
total = combination(h+w-2, h-1)
print(int(total-count)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math

# 10, 7, 3, 4
H, W, A, B = map(int, input().split())

# 通らなければいけない点を算出する
need = [[B, i] for i in range(1, H-A+1)]
ans = 0

for each in need:
    # 通らなければいけない点までの計算
    left = each[0] - 1
    top  = each[1] - 1
    C1 = (math.factorial(top+left))/(math.factorial(top)*math.factorial(left))

    # それ以降の計算
    left = W - B - 1
    top  = H - top - 1
    C2 = math.factorial((top+left))/(math.factorial(top)*math.factorial(left))
    
    ans += (C1*C2)

print(int(ans))

Submission status: Runtime Error

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

fact = [1] * (h + w + 1)
invf = [1] * (h + w + 1)
invn = [1] * (h + w + 1)
for i in range(1, h + w + 1):
  fact[i] = fact[i-1] * i % mod
  invn[i] = -invn[mod % i] * (p // i) % mod
  invf[i] = invf[i-1] * invn[i] % mod

count = 0
for i in range(min(h-a, w-b)):
  count += fact[h+b-a-1] * invf[h-a-i-1] * invf[b+i] * fact[w+a-b-1] * invf[a+i] * invf[w-b-i-1]
  count %= mod
print(count)

Submission status: Runtime Error

Solution code:
import math as m
import sys

s=input()
l1=s.split()
h=int(l1[0])
w=int(l1[1])
a=int(l1[2])
b=int(l1[3])
sum1=0
sum2=0
for i in range(a+1,h+1):
    sum1=0
    sum1+=(m.factorial(i+w-b-2))/(m.factorial(i-1)*m.factorial(w-b-1))
    sum1*=(m.factorial(h-i+w-b))/(m.factorial(h-i)*m.factorial((w-b)))
    sum2+=sum1

print(int(sum2))

Submission status: Runtime Error

Solution code:
import math as m
import sys
from tkinter import *


s=input()
l1=s.split()
h=int(l1[0])
w=int(l1[1])
a=int(l1[2])
b=int(l1[3])
sum1=0
sum2=0
for i in range(a+1,h+1):
    sum1=0
    sum1+=(m.factorial(i+w-b-2))/(m.factorial(i-1)*m.factorial(w-b-1))
    sum1*=(m.factorial(h-i+w-b))/(m.factorial(h-i)*m.factorial((w-b)))
    sum2+=sum1

print(int(sum2))

Submission status: Runtime Error

Solution code:
import math as m
import sys

s=input()
l1=s.split()
h=int(l1[0])
w=int(l1[1])
a=int(l1[2])
b=int(l1[3])
sum1=0
sum2=0
for i in range(a+1,h+1):
    sum1=0
    sum1+=(m.factorial(i+w-b-2))/(m.factorial(i-1)*m.factorial(w-b-1))
    sum1*=(m.factorial(h-i+w-b))/(m.factorial(h-i)*m.factorial((w-b)))
    sum2+=sum1

print(sum2)

Submission status: Runtime Error

Solution code:
import math as m
import sys
from tkinter import *


s=input()
l1=s.split()
h=int(l1[0])
w=int(l1[1])
a=int(l1[2])
b=int(l1[3])
sum1=0
sum2=0
for i in range(a+1,h+1):
    sum1=0
    sum1+=(m.factorial(i+w-b-2))/(m.factorial(i-1)*m.factorial(w-b-1))
    sum1*=(m.factorial(h-i+w-b))/(m.factorial(h-i)*m.factorial((w-b)))
    sum2+=sum1

print(sum2)

Submission status: Runtime Error

Solution code:
import math
h, w, a, b = map(int, input().split())
st1 = math.factorial(h+w) / (math.factorial(h) * math.factorial(w))
st2 = math.factorial(a+b) / (math.factorial(a) * math.factorial(b))
total = st1 - st2
wari = 10**9 + 7
print(total % wari)

Submission status: Runtime Error

Solution code:
h, w, a, b = map(int, input().split(' '))
MOD = 10**9 + 7
MAX = int(1.8*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: Runtime Error

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

MOD = 10**9 + 7

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


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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import sys
sys.float_info.max
H, W, A, B = map(int, input().split())

StoB = np.zeros(B)
BtoE = np.zeros(B)
sum = 0
# print(StoB)
# print(BtoE)
all = math.factorial(H + W - 2) / (math.factorial(H - 1) * math.factorial(W - 1))
# print(all)
for i in range(B):
    # print(i)
    # print(H - A)
    StoB[i] = math.factorial((i) + (H - A - 1)) / (math.factorial(i) * math.factorial(H - A - 1))
    # print(StoB[i])
# print(StoB)
    BtoE[i] = math.factorial((W - i) + A - 2) / (math.factorial(W - i - 1) * math.factorial(A - 1))
# print(BtoE)
    sum += StoB[i] * BtoE[i]
print(int(all - sum) % (10 ** 9 - 7))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import sys
sys.float_info.max
H, W, A, B = map(int, input().split())

StoB = np.zeros(B)
BtoE = np.zeros(B)
sum = 0
# print(StoB)
# print(BtoE)
all = math.factorial(H + W - 2) / (math.factorial(H - 1) * math.factorial(W - 1))
# print(all)
for i in range(B):
    # print(i)
    # print(H - A)
    StoB[i] = math.factorial((i) + (H - A - 1)) / (math.factorial(i) * math.factorial(H - A - 1))
    # print(StoB[i])
# print(StoB)
    BtoE[i] = math.factorial((W - i) + A - 2) / (math.factorial(W - i - 1) * math.factorial(A - 1))
# print(BtoE)
    sum += StoB[i] * BtoE[i]
print(int(all - sum) / (10 ** 9 - 7))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import sys
sys.float_info.max
H, W, A, B = map(int, input().split())

StoB = np.zeros(B)
BtoE = np.zeros(B)
sum = 0
# print(StoB)
# print(BtoE)
all = math.factorial(H + W - 2) / (math.factorial(H - 1) * math.factorial(W - 1))
# print(all)
for i in range(B):
    # print(i)
    # print(H - A)
    StoB[i] = math.factorial((i) + (H - A - 1)) / (math.factorial(i) * math.factorial(H - A - 1))
    # print(StoB[i])
# print(StoB)
    BtoE[i] = math.factorial((W - i) + A - 2) / (math.factorial(W - i - 1) * math.factorial(A - 1))
# print(BtoE)
    sum += StoB[i] * BtoE[i]
print(int(all - sum))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import sys
sys.float_info.max
H, W, A, B = map(int, input().split())

StoB = np.zeros(B)
BtoE = np.zeros(B)
sum = 0
# print(StoB)
# print(BtoE)
all = math.factorial(H + W - 2) / (math.factorial(H - 1) * math.factorial(W - 1))
# print(all)
for i in range(B):
    # print(i)
    # print(H - A)
    StoB[i] = math.factorial((i) + (H - A - 1)) / (math.factorial(i) * math.factorial(H - A - 1))
    # print(StoB[i])
# print(StoB)
    BtoE[i] = math.factorial((W - i) + A - 2) / (math.factorial(W - i - 1) * math.factorial(A - 1))
# print(BtoE)
    sum += StoB[i] * BtoE[i]
print(all - sum)

Submission status: Runtime Error

Solution code:
import math

h,w,a,b =map(int,input().split())
ans = 0
area1 = b-1
area2 = w+h-b-2

for j in range(h-a):
    ans1 = math.factorial(area1+j)/(math.factorial(area1)*math.factorial(j))
    ans2 = math.factorial(area2-j)/(math.factorial(area2-h+1)*math.factorial(h-1-j))
    ans += ans1*ans2
    

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

Submission status: Runtime Error

Solution code:
import math

h,w,a,b =map(int,input().split())
ans = 0
area1 = b-1
area2 = w+h-b-2

for j in range(h-a):
    ans1 = math.factorial(area1+j)/(math.factorial(area1)*math.factorial(j))
    ans2 = math.factorial(area2-j)/(math.factorial(area2-h+1)*math.factorial(h-1-j))
    ans += ans1*ans2
    

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

Submission status: Runtime Error

Solution code:
nums = input().split()
H = int(nums[0])
W = int(nums[1])
A = int(nums[2])
B = int(nums[3])

from math import factorial

#全体
total = factorial(H + W -2) / factorial(W-1) / factorial(H - 1)

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

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

answer = int(total - forbidden)
print(answer % ((10 ** 9) + 7))