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;
}