fq.cpp

#include<cstdio>
#include<cstdlib>
#include<cstring>
 
#include<cmath>
#include<cctype>
#include<climits>
#include<algorithm>
#include<utility>
#include<string>
 
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
 
 
using namespace std;
 
#define REP(i,N) for (int i = 0; i < (N); i++)
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORI(i,a,b) for (int i = (a); i < (b); i++)
#define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
#define DP(arg...) fprintf(stderr, ## arg)
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
 
#define MOD 1000000
 
ll D[1111][1111];
int n;
char s[1111];
 
void solve() {
	n = strlen(s+1);
	REP(i, n+5) REP(j, n+5) D[i][j] = 0;
	D[0][0] = 1;
	FOR (i, 1, n) {
		FOR(j, 0, n) {
			if (s[i]=='(' || s[i]=='.') {
				D[i][j+1] += D[i-1][j];
				D[i][j+1] %= MOD;
			}
			if ((s[i]==')' || s[i]=='.') && j>0) {
				D[i][j-1] += D[i-1][j];
				D[i][j-1] %= MOD;
			}
		}
	}
	/*REP(i, n+1) {
		REP(j, n+1) printf("%lld ", D[i][j]); printf("\n");
	}*/
	printf("%lld\n", D[n][0]);
}
 
int main() {
	while (scanf(" %s", s+1) != EOF) {
		solve();
	}
	return 0;
}