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

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

    static class FBracketSubstring {
        int n;
        char[] arr;
        int[] pi;
        long[][][] memo;
        int mod = (int) 1e9 + 7;

        void prefixFunction() {
            int n = arr.length;
            pi = new int[n];
            for (int i = 1, j = 0; i < n; ++i)        //j = pi[i-1] at the beginning of every iteration
            {
                while (j > 0 && arr[i] != arr[j])
                    j = pi[j - 1];
                if (arr[i] == arr[j])
                    ++j;
                pi[i] = j;
            }
        }

        public void readInput(Scanner sc) {
            n = sc.nextInt();
            arr = sc.next().toCharArray();

        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int q = 1;
            while (q-- > 0) {
                readInput(sc);
                prefixFunction();
                memo = new long[2 * n][2 * n][2 * n];
                for (long[][] x : memo)
                    for (long[] y : x)
                        Arrays.fill(y, -1);
                pw.println(dp(0, 0, 0));
            }
        }

        private long dp(int idx, int prefix, int match) {
            if (idx == 2 * n)
                return prefix == 0 && match == arr.length ? 1 : 0;
            if (memo[idx][prefix][match] != -1)
                return memo[idx][prefix][match];
            int next = getNext(match, '(');
            long open = dp(idx + 1, prefix + 1, next);
            next = getNext(match, ')');
            long close = prefix > 0 ? dp(idx + 1, prefix - 1, next) : 0;
            return memo[idx][prefix][match] = (open + close) % mod;
        }

        private int getNext(int match, char c) {
            int next = match;
            if (match != arr.length) {
                if (arr[match] == c)
                    next++;
                else {
                    while (match != 0) {
                        match = pi[match - 1];
                        if (arr[match] == c)
                            break;
                    }
                    if (arr[match] == c)
                        next = match + 1;
                    else
                        next = match;
                }
            }
            return next;
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

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

    }
}

