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;
template <typename T, typename S>
ostream& operator<<(ostream& os, const pair<T, S>& v) {
  os << "(" << v.first << "," << v.second << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  long long sz = v.size();
  for (long long i = 0; i < sz; ++i) {
    os << v[i];
    if (i != sz - 1) os << ",";
  }
  os << "]\n";
  return os;
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
const long long N = 301;
long long n;
string str;
long long len[N][2];
const long long mod = 1e9 + 7;
long long dp[202][202][202][2];
long long sz;
long long solve(long long idx, long long balance, long long matched,
                long long once) {
  long long& res = dp[idx][balance][matched][once];
  if (res != -1) return res;
  res = 0;
  if (idx == n + n + 1) {
    if (balance == 0 and once) return res = 1;
    return res = 0;
  }
  res = (res + solve(idx + 1, balance + 1, len[matched][0],
                     (once | len[matched][0] == sz))) %
        mod;
  if (balance > 0) {
    res = (res + solve(idx + 1, balance - 1, len[matched][1],
                       (once | len[matched][1] == sz))) %
          mod;
  }
  return res;
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  cin >> n;
  cin >> str;
  sz = str.size();
  str = " " + str;
  if (str[1] == '(')
    len[0][0] = 1;
  else
    len[0][1] = 1;
  string pref = "";
  auto calc = [](string& pref) {
    long long bla = pref.size(), ans = 0;
    for (long long i = 1; i < bla + 1; ++i) {
      if (str.substr(1, i) == pref.substr(bla - i, i)) {
        ans = max(ans, i);
      }
    }
    return ans;
  };
  for (long long i = 1; i < sz + 1; ++i) {
    pref += str[i];
    pref += "(";
    len[i][0] = calc(pref);
    pref.pop_back();
    pref += ")";
    len[i][1] = calc(pref);
    pref.pop_back();
  }
  memset(dp, -1, sizeof(dp));
  cout << solve(1, 0, 0, 0) << endl;
  return 0;
}
