#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define Debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
typedef unsigned int uint;
typedef pair <int, int> pii;
typedef unsigned long long uLL;
template <typename T> inline void Read(T &x) {
char c = getchar();
bool f = false;
for (x = 0; !isdigit(c); c = getchar()) {
if (c == '-') {
f = true;
}
}
for (; isdigit(c); c = getchar()) {
x = x * 10 + c - '0';
}
if (f) {
x = -x;
}
}
template <typename T> inline bool CheckMax(T &a, const T &b) {
return a < b ? a = b, true : false;
}
template <typename T> inline bool CheckMin(T &a, const T &b) {
return a > b ? a = b, true : false;
}
const int N = 305;
const int mod = 1e9 + 7;
int n, ans, a[N];
char s[N];
namespace CaseA {
int f[N][N];
int Main() {
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
if (a[i] >= 0) {
for (int j = 0; j <= i; ++j) {
f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 1; j <= i; ++j) {
f[i + 1][j - 1] = (f[i + 1][j - 1] + f[i][j]) % mod;
}
}
}
ans = (ans + f[n][0]) % mod;
return 0;
}
}
namespace CaseB {
int h[N][N], f[N][N][N][2], g[N][N][N][2];
inline void Init() {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
memset(h, 0, sizeof h);
for (int x = 0; x < n >> 1; ++x) {
f[x][0][0][!x] = 1;
for (int i = 0; i < n; ++i) {
if (a[i] >= 0) {
for (int j = 0; j < x; ++j) {
f[x][i + 1][j + 1][j + 1 == x] = (f[x][i + 1][j + 1][j + 1 == x] + f[x][i][j][0]) % mod;
f[x][i + 1][j + 1][1] = (f[x][i + 1][j + 1][1] + f[x][i][j][1]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 0; j < x; ++j) {
f[x][i + 1][j][0] = (f[x][i + 1][j][0] + f[x][i][j + 1][0]) % mod;
f[x][i + 1][j][1] = (f[x][i + 1][j][1] + f[x][i][j + 1][1]) % mod;
}
}
}
}
for (int x = 0; x < n; ++x) {
g[x][n][0][!x] = 1;
for (int i = n - 1; ~i; --i) {
if (a[i] >= 0) {
for (int j = 0; j < n; ++j) {
g[x][i][j][0] = (g[x][i][j][0] + g[x][i + 1][j + 1][0]) % mod;
}
g[x][i][x][1] = (g[x][i][x][1] + g[x][i + 1][x + 1][0]) % mod;
for (int j = x + 1; j < min(n, x << 1); ++j) {
g[x][i][j][1] = (g[x][i][j][1] + g[x][i + 1][j + 1][1]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 0; j < n; ++j) {
g[x][i][j + 1][0] = (g[x][i][j + 1][0] + g[x][i + 1][j][0]) % mod;
}
if (x) {
g[x][i][x][1] = (g[x][i][x][1] + g[x][i + 1][x - 1][0]) % mod;
}
for (int j = x; j <= min(n, x << 1); ++j) {
g[x][i][j + 1][1] = (g[x][i][j + 1][1] + g[x][i + 1][j][1]) % mod;
}
}
}
}
h[n][0] = 1;
for (int i = n - 1; ~i; --i) {
if (a[i] >= 0) {
for (int j = 0; j < n; ++j) {
h[i][j] = (h[i][j] + h[i + 1][j + 1]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 0; j < n; ++j) {
h[i][j + 1] = (h[i][j + 1] + h[i + 1][j]) % mod;
}
}
}
}
inline void Solve(int x, int y) {
for (int i = 0; i < n; i += 2) {
if (a[i] <= 0) {
if (x >= y) {
ans = (1LL * f[x][i][0][1] * h[i + 1][(y << 1) - 1] + ans) % mod;
} else {
ans = (1LL * f[x][i][0][1] * g[x + y][i + 1][(y << 1) - 1][1] + ans) % mod;
}
}
}
}
inline void Solve() {
for (int i = 0; i <= n >> 1; ++i) {
for (int j = 1; i + j <= n >> 1; ++j) {
Solve(i, j);
}
}
}
int Main() {
for (int t = 0; t < 2; ++t) {
Init(), Solve();
reverse(a, a + n);
for (int i = 0; i < n; ++i) {
a[i] = -a[i];
}
}
return 0;
}
}
namespace CaseC {
int f[N][N][N][2], g[N][N][N << 1][3];
inline void Init(int t) {
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
for (int x = 0; x < n >> 1; ++x) {
f[x][0][0][!x] = 1;
for (int i = 0; i < n; ++i) {
if (a[i] >= 0) {
for (int j = 0; j < x; ++j) {
f[x][i + 1][j + 1][j + 1 == x] = (f[x][i + 1][j + 1][j + 1 == x] + f[x][i][j][0]) % mod;
f[x][i + 1][j + 1][1] = (f[x][i + 1][j + 1][1] + f[x][i][j][1]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 0; j < x; ++j) {
f[x][i + 1][j][0] = (f[x][i + 1][j][0] + f[x][i][j + 1][0]) % mod;
f[x][i + 1][j][1] = (f[x][i + 1][j][1] + f[x][i][j + 1][1]) % mod;
}
}
}
}
for (int x = 0; x < n >> 1; ++x) {
g[x][n][n][!x && !t] = 1;
for (int i = n - 1; ~i; --i) {
if (a[i] >= 0) {
for (int j = 1; j < n; ++j) {
g[x][i][j - 1 + n][0] = (g[x][i][j - 1 + n][0] + g[x][i + 1][j + n][0]) % mod;
}
for (int j = 0; j < n; ++j) {
g[x][i][j - 1 + n][1 + (!j)] = (g[x][i][j - 1 + n][1 + (!j)] + g[x][i + 1][j + n][1]) % mod;
}
for (int j = -n + 1; j <= x << 1; ++j) {
g[x][i][j - 1 + n][2] = (g[x][i][j - 1 + n][2] + g[x][i + 1][j + n][2]) % mod;
}
}
if (a[i] <= 0) {
for (int j = 0; j < n; ++j) {
g[x][i][j + 1 + n][j + 1 == x + t] = (g[x][i][j + 1 + n][j + 1 == x + t] + g[x][i + 1][j + n][0]) % mod;
}
for (int j = 0; j < n; ++j) {
g[x][i][j + 1 + n][1] = (g[x][i][j + 1 + n][1] + g[x][i + 1][j + n][1]) % mod;
}
for (int j = -n; j < x << 1; ++j) {
g[x][i][j + 1 + n][2] = (g[x][i][j + 1 + n][2] + g[x][i + 1][j + n][2]) % mod;
}
}
}
}
}
inline void Solve(int x, int y) {
for (int i = 0; i < n; i += 2) {
if (a[i] <= 0) {
ans = (1LL * f[x][i][0][1] * g[x + y][i + 1][(y << 1) - 1 + n][2] + ans) % mod;
}
}
}
inline void Solve() {
for (int i = -(n >> 1) + 1; i < (n >> 1); ++i) {
for (int j = max(0, -i); j + abs(i) <= n >> 1; ++j) {
Solve(j, i);
}
}
}
int Main() {
for (int t = 0; t < 2; ++t) {
Init(t), Solve();
reverse(a, a + n);
for (int i = 0; i < n; ++i) {
a[i] = -a[i];
}
}
return 0;
}
}
int main() {
#ifdef wxh010910
freopen("d.in", "r", stdin);
#endif
Read(n), scanf("%s", s);
if (n & 1) {
puts("0");
return 0;
}
for (int i = 0; i < n; ++i) {
if (s[i] == '(') {
a[i] = 1;
} else if (s[i] == ')') {
a[i] = -1;
} else {
a[i] = 0;
}
}
CaseA::Main();
CaseB::Main();
CaseC::Main();
printf("%d\n", ans);
#ifdef wxh010910
Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
return 0;
}
Compilation message
securitygate.cpp: In function 'int main()':
securitygate.cpp:249:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
Read(n), scanf("%s", s);
~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
256 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
