You are given a bracket sequence s (not necessarily a regular one). A bracket sequence is a string containing only characters '(' and ')'.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.

Your problem is to calculate the number of regular bracket sequences of length 2n containing the given bracket sequence s as a substring (consecutive sequence of characters) modulo 10^9+7 (1000000007).

Input

The first line of the input contains one integer n (1 ≤ n ≤ 100) — the half-length of the resulting regular bracket sequences (the resulting sequences must have length equal to 2n).

The second line of the input contains one string s (1 ≤ |s| ≤ 200) — the string s that should be a substring in each of the resulting regular bracket sequences (|s| is the length of s).

Output

Print only one integer — the number of regular bracket sequences containing the given bracket sequence s as a substring. Since this number can be huge, print it modulo 10^9+7 (1000000007).

Examples

Input

5
()))()


Output

5


Input

3
(()


Output

4


Input

2
(((


Output

0

Note

All regular bracket sequences satisfying the conditions above for the first example: 

  * "(((()))())"; 
  * "((()()))()"; 
  * "((()))()()"; 
  * "(()(()))()"; 
  * "()((()))()". 



All regular bracket sequences satisfying the conditions above for the second example: 

  * "((()))"; 
  * "(()())"; 
  * "(())()"; 
  * "()(())". 



And there is no regular bracket sequences of length 4 containing "(((" as a substring in the third example.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using VI = vector<int>;
using VL = vector<long long>;
using VVI = vector<VI>;
using VVL = vector<VL>;
using MII = map<int, int>;
using MIVI = map<int, VI>;
using MLL = map<LL, LL>;
int READ_INT() {
  int temp;
  cin >> temp;
  return temp;
}
LL READ_LONG() {
  LL temp;
  cin >> temp;
  return temp;
}
string READ_STRING() {
  string temp;
  cin >> temp;
  return temp;
}
const LL MOD = LL(1e9) + 7;
const int INF = 1e9 + 5;
const double PI = acos(-1.0);
const double EPS = 1e-9;
int n, m;
string s;
string org;
LL dp[205][205][205];
void create_org() {
  for (auto c : s) {
    if (c == '(')
      org += "1";
    else
      org += "0";
  }
}
LL dp2[205][205];
LL total_count(int ind, int f) {
  if (ind == 2 * n) return (f == 0);
  if (f < 0) return 0;
  if (dp2[ind][f] != -1) return dp2[ind][f];
  return dp2[ind][f] =
             (total_count(ind + 1, f + 1) + total_count(ind + 1, f - 1)) % MOD;
}
LL dp3[205][2];
void fill_dp3() {
  memset(dp3, 0, sizeof(dp3));
  for (int l = 0; l <= m; ++l) {
    string cur1 = org.substr(0, l) + "1";
    string cur2 = org.substr(0, l) + "0";
    for (int x = 0; x < cur1.size(); ++x) {
      string suf = cur1.substr(x, (cur1.size() - x));
      string par = org.substr(0, cur1.size() - x);
      if (suf == par) {
        dp3[l][1] = cur1.size() - x;
        break;
      }
    }
    for (int x = 0; x < cur2.size(); ++x) {
      string suf = cur2.substr(x, (cur2.size() - x));
      string par = org.substr(0, cur2.size() - x);
      if (suf == par) {
        dp3[l][0] = cur1.size() - x;
        break;
      }
    }
  }
}
LL count(int ind, int match_len, int f) {
  if (match_len >= m) {
    return 0;
  }
  if (ind == 2 * n) return (f == 0);
  if (f < 0) return 0;
  if (dp[ind][match_len][f] != -1)
    return dp[ind][match_len][f];
  else {
    LL l, r;
    if (org[match_len] == '(')
      count(ind + 1, match_len + 1, f + 1);
    else
      l = count(ind + 1, dp3[match_len][1], f + 1);
    if (org[match_len] == ')')
      r = count(ind + 1, match_len + 1, f - 1);
    else
      r = count(ind + 1, dp3[match_len][0], f - 1);
    return dp[ind][match_len][f] = (l + r) % MOD;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  cin >> s;
  m = s.size();
  create_org();
  fill_dp3();
  memset(dp2, -1, sizeof(dp2));
  LL tot = total_count(0, 0);
  memset(dp, -1, sizeof(dp));
  LL neg = count(0, 0, 0);
  cout << (tot - neg + MOD) % MOD << "\n";
  return 0;
}
