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;
typedef priority_queue<long long, vector<long long>, greater<long long>>
    minHeap;
const int INF = 1e9 + 9;
const long long LINF = 1e17 + 9;
const long long MD = 1000000007;
inline long long mul(long long a, long long b) { return (a * b) % MD; }
inline long long po(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) ans = mul(ans, a);
    a = mul(a, a);
    b /= 2;
  }
  return ans;
}
const int N = 2e2 + 33;
long long n, m, k, t;
long long arr[N];
string s;
int lps[N][2], LPS[N];
long long dp[N][N][N][2];
long long f(int i, int l, int sum, int is) {
  if (sum < 0) return 0;
  if (dp[i][l][sum][is] != -1) return dp[i][l][sum][is];
  if (i == n && sum == 0 && is) {
    return 1;
  }
  if (i == n) return 0;
  long long res = 0;
  res =
      (res + f(i + 1, lps[l][0], sum + 1, ((lps[l][0] == s.size()) | is))) % MD;
  if (sum > 0)
    res = (res + f(i + 1, lps[l][1], sum - 1, ((lps[l][1] == s.size()) | is))) %
          MD;
  return dp[i][l][sum][is] = res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  cout << fixed;
  cout << setprecision(8);
  cerr << "N"
       << " is " << N << endl;
  cin >> n >> s;
  n *= 2;
  memset(dp, -1, sizeof dp);
  LPS[0] = -1;
  for (int i = 1; i < s.size(); i++) {
    LPS[i] = LPS[i - 1];
    while (~LPS[i] && s[LPS[i] + 1] != s[i]) LPS[i] = LPS[LPS[i]];
    if (s[LPS[i] + 1] == s[i]) LPS[i]++;
  }
  lps[0][0] = s[0] == '(' ? 1 : 0;
  lps[0][1] = 1 ^ lps[0][0];
  for (int i = 1; i <= s.size(); i++) {
    if (s[i] == '(') {
      if (i < s.size()) lps[i][0] = i + 1;
      lps[i][1] = LPS[i - 1];
      while (~lps[i][1] && s[lps[i][1] + 1] != ')') lps[i][1] = LPS[lps[i][1]];
      lps[i][1]++;
      if (s[lps[i][1]] == ')') lps[i][1]++;
    } else {
      lps[i][1] = i + 1;
      lps[i][0] = LPS[i - 1];
      while (~lps[i][0] && s[lps[i][0] + 1] != '(') lps[i][0] = LPS[lps[i][0]];
      lps[i][0]++;
      if (s[lps[i][0]] == '(') lps[i][0]++;
    }
  }
  cout << f(0, 0, 0, 0) << endl;
  return 0;
}
