# Yuki 389 ロジックパズルの組み合わせ ( Combinatorics, Math )

No.389 ロジックパズルの組み合わせ - yukicoder

1 ≤ M < 1e6
0 ≤ H[ i ]
SIGMA{ H } ≤ M

O( N lg MOD7 ) / O( N )

```const int MOD7 = ( int ) 1e9 + 7;

int M;
vi H;

void init(){
cin >> M;
int h;
while( cin >> h )
if( h )
H.emplace_back( h );
}

int n, m;
int sum_h;

int int_pow( int v, int p ){
int res = v != 0 or p == 0;
while( p ){
if( p & 1 )
res = 1LL * res * v % MOD7;
p >>= 1;
v = 1LL * v * v % MOD7;
}
return res;
}

int mod_inv( int v ){
return int_pow( v, MOD7 - 2 );
}

int comb( int n, int m ){
int res = 1;
for( int i = 2; i <= n; ++i )
res = 1LL * res * i % MOD7;
for( int i = 2; i <= m; ++i )
res = 1LL * res * mod_inv( i ) % MOD7;
for( int i = 2; i <= n - m; ++i )
res = 1LL * res * mod_inv( i ) % MOD7;
return res;
}

void preprocess(){
for( int i = 0; i < H.size(); ++i )
sum_h += H[ i ];
n = M - ( sum_h + H.size() - 1 ); // number of free balls
m = H.size() + 1; // number of choices to put free balls
if( n < 0 )
cout << "NA" << endl, exit( 0 );
}

void solve(){
cout << comb( m + n - 1, n ) << endl;
}
```