fq.cpp
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <queue>
using namespace std;
int catalan(int n){
int c=1;
for (int i=1; i<=n;i++)
c=4*c-6*c/(i+1);
return c;
}
vector< vector<bool> > ok;//kam muze zavorka
int main()
{
vector<vector<int> > v;
string s;
while(cin>>s){
//ok.clear();
//ok.resize(s.size());
v.clear();
v.resize(s.size());
for(int i=0;i<s.size();i++){
// ok[i].resize(s.size());
v[i].resize(s.size());
for(int j=0;j<s.size();j++)
{
v[i][j]=0;
//ok[i][j]=true;
//ok[j][i]=true;
//if(s[j]=='.'){
//ok[i][j]=true;
//}
//else
// if(s[j]=='('){
// ok[i][j]==false;
// }
// else{
// ok[j][i]=false;
// }
}
}//end init for
//dynamika
v[0][0]=1;
for(int i=0;i<=s.size()/2;i++){
for(int j=0;j<=i;j++){
/*if(j>0&&ok[i][j-1])
v[i][j]+=v[i][j-1];
if(i>0&&ok[i-1][j])
v[i][j]+=v[i-1][j];*/
if(j>0&&s[i+j-1]!='(')
v[i][j]+=v[i][j-1];
if(i!=j&&s[i+j-1]!=')')
v[i][j]+=v[i-1][j];
v[i][j]%=1000000;
}
}
cout<<v[s.size()/2][s.size()/2]<<endl;
//cout<<catalan(s.size()/2)<<endl;
}
return 0;
}