fq.cpp
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <bitset>
#include <string>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef set<int> si;
typedef set<ii> sii;
#define MP make_pair
#define PB push_back
#define REP(i,a) for ( int i = 0; i < int(a); i++)
#define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++)
#define FORD(i,a,b) for(int i= int(a); i>=int(b); i--)
const int INF = 1<<29;
typedef long long int ll;
char line[1024];
int len, half;
const int MOD = 1000000;
int tab[1002][504];
int rec(int misto, int idx, int five){
int out = 0;
//printf("%d %d\n", misto, idx);
if ( five > half) return 0;
if ( tab[misto][idx] >= 0 )
return tab[misto][idx];
if ( idx >= half ) {
return 1;
}
if ( misto >= len -1) {
return idx==1 && line[misto] != '(' ;
}
if (line[misto] == '.' ) {
if ( idx == 0 )
out += rec(misto+1, idx+1, five+1);
else {
out += rec(misto+1, idx+1, five+1);
out += rec(misto+1, idx-1, five);
}
}
else if ( line[misto] == '(' ) {
out += rec(misto+1, idx+1, five+1);
}
else {
if ( idx == 0 ) return 0;
out += rec(misto+1, idx-1, five);
}
tab[misto][idx] = out%MOD;
return out%MOD;
}
void clear(){
FOR(i,0,len)
FOR(j,0,half+1)
tab[i][j]=-1;
}
int main(){
while ( scanf(" %s", line) > 0 ) {
len = strlen(line);
half = len/2;
clear();
printf("%d\n", rec(0,0,0)) ;
}
return 0;
}