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>
int b;
long long int check[210][210][210];
char x[210];
int fail[210];
long long int func(int s, int t, int k) {
  int l = t - s;
  if (s < 0) return 0;
  if (t < 0) return 0;
  if (l < 0) return 0;
  if (k == b) return 0;
  if (s == 0 && t == 0) return 1;
  if (check[s][t][k] != -1) return check[s][t][k];
  long long int s1, s2;
  int p = k;
  while (1) {
    if (x[p + 1] == '(') {
      s1 = func(s - 1, t, p + 1);
      goto u;
    } else if (p == 0)
      break;
    else
      p = fail[p];
  }
  s1 = func(s - 1, t, 0);
u:;
  p = k;
  while (1) {
    if (x[p + 1] == ')') {
      s2 = func(s, t - 1, p + 1);
      goto v;
    } else if (p == 0)
      break;
    else
      p = fail[p];
  }
  s2 = func(s, t - 1, 0);
v:;
  return check[s][t][k] = (s1 + s2) % 1000000007;
}
long long int check2[210][210];
long long int comb(int s, int t) {
  if (t == 0) return 1;
  if (s == t) return 1;
  if (check2[s][t]) return check2[s][t];
  return check2[s][t] = (comb(s - 1, t - 1) + comb(s - 1, t)) % 1000000007;
}
long long int power(long long int a, long long int b) {
  long long int ans = 1;
  long long int k = a;
  while (b) {
    if (b % 2 == 1) ans *= k, ans %= 1000000007;
    b /= 2;
    k *= k, k %= 1000000007;
  }
  return ans;
}
long long int inv(long long int k) { return power(k, 1000000007 - 2); }
int main() {
  for (int i = 0; i <= 200; i++)
    for (int j = 0; j <= 200; j++)
      for (int k = 0; k <= 200; k++) check[i][j][k] = check[i][j][k] = -1;
  int a;
  scanf("%d", &a);
  scanf("%s", x + 1);
  b = strlen(x + 1);
  fail[1] = 0;
  for (int i = 2; i <= b; i++) {
    int t = fail[i - 1];
    while (t > 0 && x[t + 1] != x[i]) t = fail[t];
    if (x[t + 1] == x[i])
      fail[i] = t + 1;
    else
      fail[i] = 0;
  }
  long long int S = comb(2 * a, a);
  S *= inv(a + 1);
  S %= 1000000007;
  printf("%lld", (S - func(a, a, 0) + 1000000007) % 1000000007);
}
