DP で全探索．
\(dp_{i,x} := \) \([0,i)\) まで調べ終わって，値が \(x\) の場合の数．
ここで，( を +1, ) を -1 として，先頭から調べて累積和をとる． かっこ列になる必要十分条件は，常に和が 0 以上かつ，最後に和が 0になること．
遷移は，今調べている文字が (, ), ? で場合分け． ? のときは，次の文字が (,) で場合分け．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
string s; cin >> s;
ll n = s.length();
dp[0] = 1;
rep(i,n){
swap(dp, old);
rep(x,n+1){
if(s[i] == '('){
dp[x+1] += old[x];
}else if(s[i] == ')'){
if(x-1 >= 0) dp[x-1] += old[x];
}else{
dp[x+1] += old[x];
if(x-1 >= 0)dp[x-1] += old[x];
}
}
}
cout << dp[0].val() << endl;
return 0;
}
