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 <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << " = " << h << endl;
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << " = " << h << ", ";
  _dbg(sdbg + 1, a...);
}
const int maxn = (2e2) + 7;
const int maxk = 20;
const int inf = (1e9) + 7;
const long long LLinf = (1e18) + 7;
const long double eps = 1e-9;
const long long mod = 1e9 + 7;
long long dp[maxn][maxn][maxn][2];
int gdzie[maxn][5];
long long dyn(int a, int b, int c, int d) {
  if (a >= 0 && b >= 0 && c >= 0 && d >= 0 && a < maxn && b < maxn &&
      c < maxn && d < maxn)
    return dp[a][b][c][d];
  return 0LL;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  dp[0][0][0][0] = 1;
  s = "#" + s;
  for (int i = 0; i < ((int)(s).size()); i++)
    for (int k = 0; k < 2; k++) {
      string xd, wzo;
      for (int j = 1; j <= i; j++) xd.push_back(s[j]);
      wzo = xd;
      if (i + 1 < ((int)(s).size())) wzo.push_back(s[i + 1]);
      if (k == 0)
        xd.push_back('(');
      else
        xd.push_back(')');
      while (((int)(xd).size()) > 0 && xd != wzo) {
        reverse(xd.begin(), xd.end());
        xd.pop_back();
        reverse(xd.begin(), xd.end());
        while (((int)(wzo).size()) > ((int)(xd).size())) wzo.pop_back();
      }
      gdzie[i][k] = ((int)(xd).size());
    }
  for (int i = 0; i <= 2 * n; i++)
    for (int j = 0; j <= i; j++) {
      dp[i][j][((int)(s).size()) - 1][1] += dp[i][j][((int)(s).size()) - 1][0];
      dp[i][j][((int)(s).size()) - 1][0] = 0;
      for (int k = 0; k < ((int)(s).size()); k++) {
        dp[i + 1][j + 1][gdzie[k][0]][0] += dp[i][j][k][0];
        if (j > 0) dp[i + 1][j - 1][gdzie[k][1]][0] += dp[i][j][k][0];
        dp[i + 1][j + 1][gdzie[k][0]][0] %= mod;
        if (j > 0) dp[i + 1][j - 1][gdzie[k][1]][0] %= mod;
        dp[i + 1][j + 1][gdzie[k][0]][1] += dp[i][j][k][1];
        if (j > 0) dp[i + 1][j - 1][gdzie[k][1]][1] += dp[i][j][k][1];
        dp[i + 1][j + 1][gdzie[k][0]][1] %= mod;
        if (j > 0) dp[i + 1][j - 1][gdzie[k][1]][1] %= mod;
      }
    }
  long long res = 0LL;
  for (int i = 0; i <= ((int)(s).size()); i++) res += dp[2 * n][0][i][1];
  res %= mod;
  cout << res;
  return 0;
}
