#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("Ofast")
#define TASK ""
#define ll long long
#define ull unsigned ll
#define db long double
#define pLL pair<ll, ll>
#define pLI pair<ll, int>
#define pIL pair<int, ll>
#define pII pair<int, int>
#define vec vector
#define vL vec<ll>
#define vvL vec<vL>
#define vI vec<int>
#define vvI vec<vI>
#define vvvI vec<vvI>
#define vvvvI vec<vvvI>
#define vD vec<db>
#define vvD vec<vD>
#define vLL vec<pLL>
#define vLI vec<pLI>
#define vIL vec<pIL>
#define vII vec<pII>
#define vvII vec<vII>
#define vS vec<string>
#define vvS vec<vS>
#define vB vec<bool>
#define vvB vec<vB>
#define umap unordered_map
#define gphash gp_hash_table
#define mset multiset
#define pque priority_queue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define stt(a, n) a.begin(), a.begin() + n
#define stf(a, n) a.begin() + n, a.end()
#define eb emplace_back
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ins insert
#define asg assign
#define rev reverse
#define fi first
#define se second
#define th third
#define ub upper_bound
#define lb lower_bound
#define ite iterator
#define fs(n) fixed << setprecision(n)
using namespace std;
using namespace __gnu_pbds;
const ll llINF = 1e18;
const int intINF = 1e9;
const ll MOD = 1e9 + 7;
const ll LIM = 1e6;
template< class T >
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define oset ordered_set
template< class A,
class B,
class C > struct triple {
A fi; B se; C th;
triple() {}
triple(A a,B b,C c) : fi(a), se(b), th(c) {}
};
#define tIII triple<int, int, int>
#define tLLL triple<ll, ll, ll>
#define vIII vec<tIII>
#define vvIII vec<vIII>
#define vLLL vec<tLLL>
mt19937 Rand(chrono::high_resolution_clock::now().time_since_epoch().count());
vI prime, lpf;
void primeSieve(int n) { prime.asg(1, 2); lpf.asg(n + 1, 2); lpf[0] = lpf[1] = 1;
for (int i = 3; i <= n; i += 2) { if (lpf[i] == 2) { lpf[i] = i; prime.pb(i); }
for (int j = 0; j < prime.size() && i * prime[j] <= n && prime[j] <= lpf[i]; ++ j) lpf[i * prime[j]] = prime[j];
} }
vvI dvs;
void dvsSieve(int n) { dvs.asg(n + 1, vI());
for (int i = 1; i <= n; ++ i) {
for (int j = i; j <= n; j += i)
dvs[j].pb(i);
} }
template< class T > bool maximize(T &a, T b) { if (b > a) return a = b, 1; return 0; }
template< class T > bool minimize(T &a, T b) { if (b < a) return a = b, 1; return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll fastPow(ll n, ll p,
ll m = MOD) { ll r = 1; for (n %= m; p; p >>= 1) { if (p & 1) (r *= n) %= m; (n *= n) %= m; } return r; }
ll invMod(ll n,
ll m = MOD) { return fastPow(n, m - 2, m); }
ll mask(int i) { return 1LL << i; }
bool bit(ll n, int i) { return n >> i & 1LL; }
#define popcount __builtin_popcountll
#define clz __builtin_clzll
#define ctz __builtin_ctzll
//__________________________________________________________________________________________________//
void init() {}
void solve() {
int N; cin >> N;
if (N & 1) { cout << 0; return; }
string S; cin >> S;
/*
if (N <= 100) {
vvI DP;
int res = 0;
for (int i = 0; i < N; ++ i) for (int j = i; j < N; ++ j) {
string T = S;
for (int k = i; k <= j; ++ k) {
if (T[k] == '(') T[k] = ')';
else if (T[k] == ')') T[k] = '(';
}
DP.asg(N + 1, vI(N + 1)); DP[0][0] = 1;
for (int x = 0; x < N; ++ x) for (int y = 0; y <= x + 1; ++ y) {
if (T[x] == '(' && y > 0) DP[x + 1][y] = DP[x][y - 1];
if (T[x] == ')' && y < N) DP[x + 1][y] = DP[x][y + 1];
if (T[x] == 'x') {
if (y > 0) (DP[x + 1][y] += DP[x][y - 1]) %= MOD;
if (y < N) (DP[x + 1][y] += DP[x][y + 1]) %= MOD;
}
}
(res += DP[N][0]) %= MOD;
}
cout << res;
return;
}
*/
vvvI DP(2, vvI(3, vI(N + 1)));
DP[0][0][0] = 1; bool f = 1;
for (int i = 1; i <= N; ++ i, f = !f) {
DP[f].asg(3, vI(N + 1));
for (int j = 0; j <= i; ++ j) {
if (S[i - 1] == '(') {
if (j > 0) DP[f][0][j] = DP[!f][0][j - 1];
if (j < N) DP[f][1][j] = (DP[!f][1][j + 1] + DP[!f][0][j + 1]) % MOD;
if (j > 0) DP[f][2][j] = (DP[!f][2][j - 1] + DP[!f][1][j - 1]) % MOD;
}
if (S[i - 1] == ')') {
if (j < N) DP[f][0][j] = DP[!f][0][j + 1];
if (j > 0) DP[f][1][j] = (DP[!f][1][j - 1] + DP[!f][0][j - 1]) % MOD;
if (j < N) DP[f][2][j] = (DP[!f][2][j + 1] + DP[!f][1][j + 1]) % MOD;
}
if (S[i - 1] == 'x') {
if (j > 0) {
DP[f][0][j] = DP[!f][0][j - 1];
DP[f][1][j] = (DP[!f][1][j - 1] + DP[!f][0][j - 1]) % MOD;
DP[f][2][j] = (DP[!f][2][j - 1] + DP[!f][1][j - 1]) % MOD;
}
if (j < N) {
(DP[f][0][j] += DP[!f][0][j + 1]) %= MOD;
(DP[f][1][j] += (DP[!f][1][j + 1] + DP[!f][0][j + 1]) % MOD) %= MOD;
(DP[f][2][j] += (DP[!f][2][j + 1] + DP[!f][1][j + 1]) % MOD) %= MOD;
}
}
}
}
cout << ((DP[!f][1][0] + DP[!f][2][0]) % MOD + DP[!f][0][0]) % MOD;
}
signed main() {
if (fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
init();
int tests = 1;
//cin >> tests;
while (tests --) solve();
return 0;
}
Compilation message
securitygate.cpp: In function 'void primeSieve(int)':
securitygate.cpp:87:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j = 0; j < prime.size() && i * prime[j] <= n && prime[j] <= lpf[i]; ++ j) lpf[i * prime[j]] = prime[j];
| ~~^~~~~~~~~~~~~~
securitygate.cpp: In function 'int main()':
securitygate.cpp:184:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
184 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
securitygate.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
