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.util.*;
import java.io.*;
 
public class Main {
    static final int MODULO = 1_000_000_000 + 7;
    static String subsequence;
    static int[][] nextPosition;
    static int[][][][] dp;
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int maxBalance = sc.nextInt();
        int length = 2 * maxBalance;
        subsequence = sc.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]);
        }
        pw.println(sum);
        pw.flush();
    }
    
    static 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]);
    }
 
    static private int sum(int first, int second) {
        return (first + second) % MODULO;
    }

    static class GeekInteger {
        public static void save_sort(int[] array) {
            shuffle(array);
            Arrays.sort(array);
        }
 
        public static int[] shuffle(int[] array) {
            int n = array.length;
            Random random = new Random();
            for (int i = 0, j; i < n; i++) {
                j = i + random.nextInt(n - i);
                int randomElement = array[j];
                array[j] = array[i];
                array[i] = randomElement;
            }
            return array;
        }
 
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

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

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

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

    public double nextDouble() {
         return Double.parseDouble(next());
    }
    
    public String[] nextArray(int n) {
        String[] a = new String[n];
        for (int i = 0; i < n; i++)
            a[i] = next();
        return a;
    }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}
