ABC 042 D - いろはちゃんとマス目 ( Math )

D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder
シンプルでいい問題。
左下の塊上一つの行を右に沿って枚挙するだけ。答えはその塊の右上のセルからその行に沿って右に行く途中加算する 始点からそこに着く方法数 * そこから終点へ着く方法数。

int fact[ MAXH + MAXW ];

int int_pow( int x, int p ){
    int res = 1;
    while( p ){
        if( p & 1 ) res = 1LL * res * x % MOD;
        x = 1LL * x * x % MOD;
        p >>= 1;
    }
    return res;
}

int mod_inv( int x ){
    return int_pow( x, MOD - 2 );
}

int get_ways( int h, int w ){
    return 1LL * fact[ h + w - 2 ] * mod_inv( fact[ h - 1 ] ) % MOD * mod_inv( fact[ w - 1 ] ) % MOD;
}

void solve(){
    for( int i = fact[ 0 ] = 1; i < MAXH + MAXW; ++i )
        fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD;

    int H, W, A, B; cin >> H >> W >> A >> B;
    int ans = 0;

    for( int i = B + 1; i <= W; ++i )
        ( ans += 1LL * get_ways( H - A, i ) * get_ways( A, W - i + 1 ) % MOD ) %= MOD;

    cout << ans << "\n";
}