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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vadim Semenov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static final class TaskF {
        private static final int MODULO = 1_000_000_000 + 7;
        private String subsequence;
        private int[][] nextPosition;
        private int[][][][] dp;

        public void solve(int __, InputReader in, PrintWriter out) {
            int maxBalance = in.nextInt();
            int length = 2 * maxBalance;
            subsequence = in.next();
            nextPosition = new int[subsequence.length() + 1][2];
            for (int i = 0; i <= subsequence.length(); ++i) {
                for (int type = 0; type < 2; ++type) {
                    char parenthesis = "()".charAt(type);
                    int k;
                    link:
                    for (k = Math.min(subsequence.length(), i + 1); k > 0; --k) {
                        if (subsequence.charAt(k - 1) != parenthesis) continue;
                        for (int j = k - 1; j-- > 0; ) {
                            if (subsequence.charAt(j) != subsequence.charAt(i - k + 1 + j)) {
                                continue link;
                            }
                        }
                        break;
                    }
                    nextPosition[i][type] = k;
                }
            }
            dp = new int[length + 1][maxBalance + 1][subsequence.length() + 1][2];
            dp[0][0][0][0] = 1;
            for (int len = 0; len < length; ++len) {
                for (int balance = 0; balance <= Math.min(len, maxBalance); ++balance) {
                    for (int pos = 0; pos <= Math.min(len, subsequence.length()); ++pos) {
                        for (int was = 0; was < 2; ++was) {
                            if (dp[len][balance][pos][was] == 0) continue;
                            if (balance < maxBalance) {
                                update(len, balance, pos, was, '(');
                            }
                            if (balance > 0) {
                                update(len, balance, pos, was, ')');
                            }
                        }
                    }
                }
            }
            int sum = 0;
            for (int pos = 0; pos <= subsequence.length(); ++pos) {
                sum = sum(sum, dp[length][0][pos][1]);
            }
            out.println(sum);
        }

        private void update(int len, int balance, int pos, int was, char parenthesis) {
            int nextLen = len + 1;
            int nextBalance = balance + (parenthesis == '(' ? 1 : -1);
            int nextPos = nextPosition[pos]["()".indexOf(parenthesis)];
            int nextWas = was | (nextPos == subsequence.length() ? 1 : 0);
            dp[nextLen][nextBalance][nextPos][nextWas] =
                    sum(dp[nextLen][nextBalance][nextPos][nextWas], dp[len][balance][pos][was]);
        }

        private int sum(int first, int second) {
            return (first + second) % MODULO;
        }

    }

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

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(readLine());
            }
            return tokenizer.nextToken();
        }

        public String readLine() {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

    }
}

