# CFR 559 C. Gerald and Giant Chess ( DP )

Problem - C - Codeforces

1 ≤ H, W ≤ 1e5

dp[ i ] : ( 1, 1 ) 走至第 i 個禁止點，且無其他造訪的禁止點，這樣的路徑數
dp[ i ] = { ( 1, 1 ) 走至 第 i 個禁止點的不走遠路路徑數 } - SIGMA{ dp[ j ] * { 第 j 個禁止點 走至 第 i 個禁止點的不走遠路路徑數 } | j < i }

O( N ^ 2 lg( MOD ) ) / O( N ^ 2 )

```vi fact; // preprocessed factorial
vi dp; // how many ways to be here as the first blocking

int ways( int h, int w ){ // how many shortest paths to go from ( 0, 0 ) to ( h, w )
function< int ( int, int ) > fp = [ & ]( int x, int p ){
int res = 1;
while( p ){
if( p & 1 ) res = 1LL * res * x % MOD7;
p >>= 1, x = 1LL * x * x % MOD7;
}
return res;
};
function< int ( int ) > inv = [ & ]( int x ){ return fp( x, MOD7 - 2 ); };
return 1LL * fact[ h + w ] * inv( 1LL * fact[ h ] * fact[ w ] % MOD7 ) % MOD7;
}

void preprocess(){
fact = vi( ( int ) 2e5 + 1 );
for( int i = fact[ 0 ] = 1; i < fact.size(); ++i )
fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD7;
sort( A.begin(), A.end() );
dp = vi( N );
for( int i = 0; i < N; ++i ){
dp[ i ] = ways( A[ i ].first - 1, A[ i ].second - 1 );
for( int j = 0; j < i; ++j )
if( A[ j ].first <= A[ i ].first and A[ j ].second <= A[ i ].second )
( dp[ i ] -= 1LL * dp[ j ] * ways( A[ i ].first - A[ j ].first, A[ i ].second - A[ j ].second ) % MOD7 ) %= MOD7;
}
}

void solve(){
int ans = ways( H - 1, W - 1 );
for( int i = 0; i < N; ++i )
( ans -= 1LL * dp[ i ] * ways( H - A[ i ].first, W - A[ i ].second ) % MOD7 ) %= MOD7;
cout << ( ans + MOD7 ) % MOD7 << endl;
}
```