fq.cpp

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MOD 1000000
int n;
char s[1111];
int dp[1111][1111];
int solve(int pos, int opened) {
	if(pos == n) {
		if(opened == 0) return 1;
		return 0;
	}
	if(dp[pos][opened] == -1) {
		if(s[pos] == '(') {
			if(opened+1 > n/2) dp[pos][opened] = 0;
			else dp[pos][opened] = solve(pos+1, opened+1)%MOD;
		} else if(s[pos] == ')') {
			if(opened-1 < 0) dp[pos][opened] = 0;
			else dp[pos][opened] = solve(pos+1, opened-1)%MOD;
		} else {
			int ans = 0;
			if(opened+1 <= n/2) ans += solve(pos+1, opened+1)%MOD;
			if(opened-1 >= 0) ans += solve(pos+1, opened-1)%MOD;
			dp[pos][opened] = ans%MOD;
		}
	}
	return dp[pos][opened]%MOD;
}
int main() {
	char c;
	n=0;
	while(scanf("%c", &c) == 1) {
		if(c == '\n') {
			s[n] = '\0';
			memset(dp, -1, sizeof(dp));
			printf("%d\n", solve(0, 0));
			n=0;
		} else {
			s[n++] = c;
		}
	}
 
	return 0;
}