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;
inline long long mod(long long n, long long m) {
  long long ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}
long long gcd(long long a, long long b) {
  return (b == 0LL ? a : gcd(b, a % b));
}
long long exp(long long a, long long b, long long m) {
  if (b == 0LL) return 1LL;
  if (b == 1LL) return mod(a, m);
  long long k = mod(exp(a, b / 2, m), m);
  if (b & 1LL) {
    return mod(a * mod(k * k, m), m);
  } else
    return mod(k * k, m);
}
const int N = 105;
const int M = 1e9 + 7;
long long dp[N * 2][N][N * 2];
int n;
string s;
const char ch[2] = {'(', ')'};
const int v[2] = {1, -1};
vector<int> prefix_function(string s) {
  int n = (int)s.size();
  vector<int> pi(n);
  for (int i = 1; i < (n); ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}
vector<int> pi;
vector<vector<int> > aut;
void compute_automaton(string s, int alpha = 2) {
  s += '#';
  int n = (int)s.size();
  pi = prefix_function(s);
  aut.assign(n + 1, vector<int>(alpha));
  for (int i = 0; i < (n); ++i) {
    for (int c = 0; c < (alpha); ++c) {
      if (i > 0 && '(' + c != s[i])
        aut[i][c] = aut[pi[i - 1]][c];
      else
        aut[i][c] = i + ('(' + c == s[i]);
    }
  }
}
long long solve(int id, int op, int ids) {
  if (op < 0 || op > (2 * n - id + 1)) return 0;
  if (id == 2 * n + 1) {
    if (op == 0 and ids == (int)s.size()) return 1;
    return 0;
  }
  long long& x = dp[id][op][ids];
  if (x != -1) return x;
  x = 0;
  for (int i = 0; i < 2; i++) {
    if ((int)s.size() > ids) {
      int nid = (aut[ids][ch[i] - 40]);
      x += solve(id + 1, op + v[i], nid);
    } else {
      x += solve(id + 1, op + v[i], ids);
    }
  }
  x %= M;
  return x;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  cin >> s;
  compute_automaton(s);
  memset(dp, -1, sizeof(dp));
  cout << solve(1, 0, 0) << "\n";
}
