typedef unsigned int u32;
/* Parity-compressed version of the standard balance DP used by the original
* WC 2017 challenge. Fixed parentheses move the origin in O(1); a question
* mark adds the two adjacent balance states. */
static u32 storage[533350];
unsigned solve(int n, char *s) {
u32 *f = storage + 266675;
f[0] = 1;
for (int i = 0; i < n; ++i) {
int len = (i + 1 < n - i + 1 ? i + 1 : n - i + 1) / 2 + 1;
if (s[i] == '?') {
if (i & 1) {
for (int j = len; j; --j) f[j] += f[j - 1];
} else {
for (int j = 0; j < len; ++j) f[j] += f[j + 1];
}
} else if (s[i] == '(' && (i & 1)) {
--f;
f[0] = 0;
} else if (s[i] == ')' && !(i & 1)) {
++f;
f[len] = 0;
}
}
return f[0];
}