#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
int N;
int MINH, MAXH, OFF, SZ;
inline int id(int h) {
return h + OFF;
}
inline void addmod(int &a, long long b) {
a = int((a + b) % MOD);
}
vector<vector<int>> getSteps(const string &s) {
vector<vector<int>> step(N);
for (int i = 0; i < N; i++) {
if (s[i] == '(') step[i] = {+1};
else if (s[i] == ')') step[i] = {-1};
else step[i] = {+1, -1};
}
return step;
}
// Reverse the string and swap '(' <-> ')'.
// This turns right-invalid cases into left-invalid cases.
string revFlip(const string &s) {
string t;
for (int i = N - 1; i >= 0; i--) {
if (s[i] == '(') t.push_back(')');
else if (s[i] == ')') t.push_back('(');
else t.push_back('x');
}
return t;
}
// Case 1: S' is already a valid bracket sequence.
int countValid(const string &s) {
auto step = getSteps(s);
vector<int> dp(SZ), ndp(SZ);
dp[id(0)] = 1;
for (int i = 0; i < N; i++) {
fill(ndp.begin(), ndp.end(), 0);
for (int h = 0; h <= MAXH; h++) {
int val = dp[id(h)];
if (!val) continue;
for (int d : step[i]) {
int nh = h + d;
if (0 <= nh && nh <= MAXH) {
addmod(ndp[id(nh)], val);
}
}
}
dp.swap(ndp);
}
return dp[id(0)];
}
// F[p][a]:
// number of prefixes where the first negative height happens exactly at p,
// and the maximum height before p is a.
vector<vector<int>> firstNegMax(const string &s) {
auto step = getSteps(s);
vector<vector<int>> F(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> cur(N + 1, vector<int>(N + 1, 0));
vector<vector<int>> nxt(N + 1, vector<int>(N + 1, 0));
cur[0][0] = 1;
for (int pos = 1; pos <= N; pos++) {
for (auto &row : nxt) {
fill(row.begin(), row.end(), 0);
}
for (int h = 0; h <= N; h++) {
for (int mx = 0; mx <= N; mx++) {
int val = cur[h][mx];
if (!val) continue;
for (int d : step[pos - 1]) {
int nh = h + d;
if (nh < 0) {
addmod(F[pos][mx], val);
} else if (nh <= N) {
int nm = max(mx, nh);
addmod(nxt[nh][nm], val);
}
}
}
}
cur.swap(nxt);
}
return F;
}
// noNeed[i][h]:
// number of ways to fill positions i+1..N,
// starting with height h at boundary i,
// never going negative, and ending at 0.
vector<vector<int>> buildNoNeed(const string &s) {
auto step = getSteps(s);
vector<vector<int>> no(N + 1, vector<int>(SZ, 0));
no[N][id(0)] = 1;
for (int i = N - 1; i >= 0; i--) {
for (int h = 0; h <= MAXH; h++) {
long long res = 0;
for (int d : step[i]) {
int nh = h + d;
if (0 <= nh && nh <= MAXH) {
res += no[i + 1][id(nh)];
}
}
no[i][id(h)] = res % MOD;
}
}
return no;
}
// Case 2: prefix-invalid, suffix-valid.
//
// The symmetric suffix-invalid, prefix-valid case is handled by revFlip().
int countOneSide(const string &s) {
auto step = getSteps(s);
auto F = firstNegMax(s);
auto no = buildNoNeed(s);
long long ans = 0;
// t = a - finalSum / 2
//
// In shifted suffix coordinates, t is the target height of r.
for (int t = 0; t <= MAXH; t++) {
vector<vector<int>> need(N + 1, vector<int>(SZ, 0));
// need[i][h]:
// from boundary i with shifted height h,
// we still need to find the first height t,
// while staying <= 2t before that.
for (int i = N; i >= 0; i--) {
int upper = min(MAXH, 2 * t);
for (int h = 0; h <= upper; h++) {
if (h == t) {
// r is here; after r only suffix-valid is needed.
need[i][id(h)] = no[i][id(h)];
} else if (i < N) {
long long res = 0;
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += need[i + 1][id(nh)];
}
}
need[i][id(h)] = res % MOD;
}
}
}
for (int p = 1; p <= N; p++) {
for (int a = 0; a < t && a <= N; a++) {
int pref = F[p][a];
if (!pref) continue;
int finalSum = 2 * (a - t);
if (finalSum < -N || finalSum > N) continue;
// At the first negative point, original height is -1.
// Shifted height = -1 - finalSum.
int startH = 2 * (t - a) - 1;
if (startH < MINH || startH > MAXH) continue;
// Original target height:
// S[r] = a + finalSum / 2 = 2a - t.
//
// If this is negative, r must be after p.
// Otherwise it already occurs before p by continuity.
int cnt;
if (t > 2 * a) cnt = need[p][id(startH)];
else cnt = no[p][id(startH)];
ans = (ans + 1LL * pref * cnt) % MOD;
}
}
}
return ans;
}
// Case 3: invalid from both sides.
//
// strict=false counts the orientation where A + C/2 <= B.
// strict=true counts the strict opposite orientation after revFlip(),
// so equality is not double-counted.
int countBothSide(const string &s, bool strict) {
auto step = getSteps(s);
auto F = firstNegMax(s);
long long ans = 0;
for (int t = 0; t <= MAXH; t++) {
// State meanings:
//
// 0: before deciding the last negative shifted height
// 1: after last negative, before r, no height > t seen
// 2: after last negative, before r, height > t seen
// 3: after r, no height > t seen
// 4: after r, height > t seen
vector<vector<array<int, 5>>> dp(
N + 1,
vector<array<int, 5>>(SZ)
);
for (int i = 0; i <= N; i++) {
for (int z = 0; z < SZ; z++) {
dp[i][z].fill(0);
}
}
// Boundary N must have shifted height 0.
int z0 = id(0);
dp[N][z0][3] = strict ? 0 : 1;
dp[N][z0][4] = 1;
// If t = 0, r can be at the very end.
if (t == 0) {
dp[N][z0][1] = strict ? 0 : 1;
dp[N][z0][2] = 1;
}
for (int i = N - 1; i >= 0; i--) {
for (int h = MINH; h <= MAXH; h++) {
int z = id(h);
// State 0:
// We are still before the final negative point.
if (h <= 2 * t) {
long long res = 0;
// Continue waiting for the last negative.
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += dp[i + 1][id(nh)][0];
}
}
// If current h is negative, we may declare this
// boundary to be the last negative.
if (h < 0) {
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += dp[i + 1][id(nh)][1];
}
}
}
dp[i][z][0] = res % MOD;
}
// States 1, 2:
// After the last negative, before r.
// h must be nonnegative and <= 2t.
// The first time h == t is forced to be r.
if (0 <= h && h <= 2 * t) {
for (int st = 1; st <= 2; st++) {
bool seenGreater = (st == 2) || (h > t);
int contState = seenGreater ? 2 : 1;
int afterRState = seenGreater ? 4 : 3;
long long res = 0;
if (h == t) {
// Forced choice: this boundary is r.
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += dp[i + 1][id(nh)][afterRState];
}
}
} else {
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += dp[i + 1][id(nh)][contState];
}
}
}
dp[i][z][st] = res % MOD;
}
}
// States 3, 4:
// After r, only suffix-valid remains.
if (h >= 0) {
for (int st = 3; st <= 4; st++) {
bool seenGreater = (st == 4) || (h > t);
int nextState = seenGreater ? 4 : 3;
long long res = 0;
for (int d : step[i]) {
int nh = h + d;
if (MINH <= nh && nh <= MAXH) {
res += dp[i + 1][id(nh)][nextState];
}
}
dp[i][z][st] = res % MOD;
}
}
}
}
for (int p = 1; p <= N; p++) {
for (int a = 0; a <= N; a++) {
int pref = F[p][a];
if (!pref) continue;
int finalSum = 2 * (a - t);
if (finalSum < -N || finalSum > N) continue;
// Shifted height at first negative point.
int startH = 2 * (t - a) - 1;
if (startH < MINH || startH > MAXH) continue;
int cnt = dp[p][id(startH)][0];
ans = (ans + 1LL * pref * cnt) % MOD;
}
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> N >> S;
if (N % 2 == 1) {
cout << 0 << '\n';
return 0;
}
MINH = -2 * N - 2;
MAXH = 2 * N + 2;
OFF = -MINH;
SZ = MAXH - MINH + 1;
string R = revFlip(S);
long long ans = 0;
ans += countValid(S);
ans += countOneSide(S);
ans += countOneSide(R);
ans += countBothSide(S, false);
ans += countBothSide(R, true);
ans %= MOD;
cout << ans << '\n';
return 0;
}
