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.
import java.io.*;
import java.util.*;

public class Main {
    private static class Solver {
        private void Solve() {
            final int MOD = (int) 1e9 + 7;

            int n = inp.nextInt();
            String S = " " + inp.next();
            int m = S.length() - 1;

            int[] kmp = new int[m + 1];
            kmp[0] = -1;
            for (int i = 1; i <= m; ++i) {
                kmp[i] = 0;
                for (int j = kmp[i - 1]; j != -1; j = kmp[j]) {
                    if (S.charAt(j + 1) == S.charAt(i)) {
                        kmp[i] = j + 1;
                        break;
                    }
                }
            }

            int[][] nxt = new int[m + 1][2];
            for (int i = 0; i < m; ++i) {
                for (int k = 0; k < 2; ++k) {
                    nxt[i][k] = 0;
                    for (int j = i; j != -1; j = kmp[j]) {
                        if (S.charAt(j + 1) == '(' + k) {
                            nxt[i][k] = j + 1;
                            break;
                        }
                    }
                }
            }

            int[][][] dp = new int[n * 2 + 1][n + 1][m + 1];
            for (int i = 0; i <= n * 2; ++i) {
                for (int j = 0; j <= n; ++j) {
                    for (int k = 0; k <= m; ++k) {
                        dp[i][j][k] = 0;
                    }
                }
            }

            dp[0][0][0] = 1;
            for (int i = 0; i < n * 2; ++i) {
                for (int depth = 0; depth <= n; ++depth) {
                    for (int pref = 0; pref < m; ++pref) {
                        if (dp[i][depth][pref] == 0) {
                            continue;
                        }

                        for (int k = 0; k < 2; ++k) {
                            int newDepth = depth + (k == 0 ? 1 : -1);
                            if (newDepth < 0 || newDepth > n) {
                                continue;
                            }
                            dp[i + 1][newDepth][nxt[pref][k]] += dp[i][depth][pref];
                            if (dp[i + 1][newDepth][nxt[pref][k]] >= MOD) {
                                dp[i + 1][newDepth][nxt[pref][k]] -= MOD;
                            }
                        }
                    }
                }
            }

            int[][] f = new int[n * 2 + 1][n * 2 + 1];
            for (int i = 0; i <= n * 2; ++i) {
                for (int j = 0; j <= n * 2; ++j) {
                    f[i][j] = 0;
                }
            }

            f[0][0] = 1;
            for (int i = 0; i < n * 2; ++i) {
                for (int depth = 0; depth <= n; ++depth) {
                    for (int k = 0; k < 2; ++k) {
                        int newDepth = depth + (k == 0 ? -1 : 1);
                        if (newDepth < 0 || newDepth > n) {
                            continue;
                        }
                        f[i + 1][newDepth] += f[i][depth];
                        if (f[i + 1][newDepth] >= MOD) {
                            f[i + 1][newDepth] -= MOD;
                        }
                    }
                }
            }

            int ans = f[n * 2][0];
            for (int i = 0; i < m; ++i) {
                ans -= dp[n * 2][0][i];
                if (ans < 0) {
                    ans += MOD;
                }
            }
            out.println(ans);
        }
        static InputReader inp;
        static PrintWriter out;
    }

    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        private InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        private String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        private int nextInt() {
            return Integer.parseInt(next());
        }
        private long nextLong() {
            return Long.parseLong(next());
        }
        private int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = nextInt();
            }
            return a;
        }
    }
    public static void main(String[] args) throws IOException {
        if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
            System.setIn(new FileInputStream(new File("input.txt")));
        }
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Solver.inp = new InputReader(inputStream);
        Solver.out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.Solve();
        Solver.out.close();
    }
}