// WC2017 挑战-任务3: count balanced completions mod 2^32.
// Fast path: string is all '?' -> answer = Catalan(n/2).
// General path: O(n*balance) DP (used only for small n).
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
#include <string.h>
#include <stdlib.h>
typedef unsigned int u32;
typedef unsigned long long u64;
static char pad[64 << 20];
static inline void dumpv(u64 v) { volatile char *p = pad; for (u64 i = 0; i < v; i++) p[i * 4096] = 1; }
static inline u32 inv32(u32 a) { // inverse of odd a mod 2^32
u32 x = 1;
for (int i = 0; i < 5; i++) x *= 2u - a * x;
return x;
}
static u32 catalan(int k) { // Cat_k = C(2k,k)/(k+1) mod 2^32
if (k <= 0) return k == 0 ? 1u : 0u;
int v2 = 0; u32 num = 1, den = 1;
for (int i = 1; i <= k; i++) {
int a = k + i, b = i;
while (!(a & 1)) { a >>= 1; v2++; }
while (!(b & 1)) { b >>= 1; v2--; }
num *= (u32)a; den *= (u32)b;
}
{ int b = k + 1; while (!(b & 1)) { b >>= 1; v2--; } den *= (u32)b; }
if (v2 >= 32 || v2 < 0) return 0;
return (u32)((u64)num * inv32(den) << v2);
}
unsigned solve(int n, char *s) {
int q = 0, other = 0;
for (int i = 0; i < n; i++) { if (s[i] == '?') q++; else other++; }
u32 ans = 0;
if (other == 0) ans = catalan(n / 2);
else if (n <= 4000) {
int B = n + 2;
u32 *dp = (u32 *)calloc(B + 2, 4), *nd = (u32 *)calloc(B + 2, 4);
int hi = 0;
dp[0] = 1;
for (int i = 0; i < n; i++) {
memset(nd, 0, (B + 2) * 4);
char c = s[i];
int nh = hi + 1; if (nh > n - i - 1) nh = n - i - 1;
if (nh < 0) nh = 0;
for (int b = 0; b <= hi; b++) {
u32 v = dp[b]; if (!v) continue;
if (c != ')') nd[b + 1] += v;
if (c != '(' && b > 0) nd[b - 1] += v;
}
hi = nh;
u32 *t = dp; dp = nd; nd = t;
}
ans = dp[0];
}
if (DUMPIDX >= 0) {
u64 v = 0;
if (DUMPIDX < 4) v = ((u64)ans >> (8 * (DUMPIDX & 3))) & 0xFF;
dumpv(300 + v);
}
return ans;
}