# CFR 785 D. Anton and School - 2 ( Math )

Problem - D - Codeforces

The only line of the input contains a string s — the bracket sequence given in Anton's homework. The string consists only of characters "(" and ")" (without quotes). It's guaranteed that the string is not empty and its length doesn't exceed 200 000.

O( | S | )

#include <bits/stdc++.h>
using namespace std;

const int MOD = ( int ) 1e9 + 7;
const int MAXLEN = ( int ) 2e5;

string seq;
int l_pfx[ MAXLEN + 1 ];
int r_pfx[ MAXLEN + 1 ];

int fact[ MAXLEN ];
int inv_fact[ MAXLEN ];

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

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

int C( int n, int r ){
return 1LL * fact[ n ] * inv_fact[ n - r ] % MOD * inv_fact[ r ] % MOD;
}

signed main(){
{
for( int i = fact[ 0 ] = inv_fact[ 0 ] = 1; i < MAXLEN; ++i ){
fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD;
inv_fact[ i ] = mod_inv( fact[ i ] );
}
}
ios::sync_with_stdio( 0 );
cin >> seq;
{
for( int i = 0; i < seq.size(); ++i ){
l_pfx[ i + 1 ] = l_pfx[ i ] + ( seq[ i ] == '(' );
r_pfx[ i + 1 ] = r_pfx[ i ] + ( seq[ i ] == ')' );
}
}
int ans = 0;
for( int i = 0; i < seq.size(); ++i ){
if( seq[ i ] == '(' ){
int ll = l_pfx[ i ];
int rr = r_pfx[ seq.size() ] - r_pfx[ i + 1 ];
( ans += C( ll + rr, rr - 1 ) ) %= MOD;
}
}
cout << ans << endl;
return 0;
}