queue.cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int dp[600][600];
char people[1042];
int l,lh;
void vypis(){
for( int i = 0; i <= lh ; i++ )
{
for( int j = 0; j <= lh; j++ )
printf("%d ",dp[i][j]);
putchar('\n');
}
}
void solve(){
lh = l / 2;
for(int i = 0; i <= lh; i++ ){
for( int j =0; j <=lh; j++ )
dp[i][j] = 0;
}
// for( int i = 0; i <=lh; i++ ){
// dp[0][i] = 1;
// dp[i][0] = 1;
// }
dp[0][0] = 1;
// vypis();
int i = 0,j = 0;
for( ; i <=lh ; i++ ){
for( j = 0; j <= i; j++ ){
if(people[i+j]=='.'||people[i+j]=='('){
if((i+1)<=lh){
dp[i+1][j]+=dp[i][j];
dp[i+1][j]%=1000000;
}
}
if(people[i+j]=='.'||people[i+j]==')'){
if(((j+1)<=i)){
dp[i][j+1]+=dp[i][j];
dp[i][j+1]%=1000000;
}
}
}
}
//vypis();
printf("%d\n",dp[lh][lh]);
}
int main(int argc, char * argv[]){
while(gets(people)){
l = strlen(people);
solve();
}
return 0;
}