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

public class BracketSubstring_CF1015F {

	static String s;
	static int len;
	static int sub;

	static int memo[][][];
	static final int MOD = (int) 1e9 + 7;

	static int fail[];
	static char[] pat;

	static void pattern() {
		int len = pat.length;
		fail = new int[len];
		fail[0] = 0;
		int k = 0;
		for (int i = 1; i < len; i++) {
			while (k > 0 && pat[i] != pat[k])
				k = fail[k - 1];

			if (pat[i] == pat[k])
				fail[i] = ++k;
			else
				fail[i] = k;
		}
	}

	static int dp(int i, int count, int commpr) {

		boolean used = commpr == sub;
		if (i == len) {
			return count == 0 && used ? 1 : 0;
		}

		if (count < 0 || Math.abs(count) > len - i)
			return 0;
		
		if(!used && len - i < sub - commpr){
			return 0;
		}

		if (memo[i][count][commpr] != -1) {
			return memo[i][count][commpr];
		}
		int commpr1 = commpr;
		if (!used) {
			while (commpr1 > 0 && pat[commpr1] != '(')
				commpr1 = fail[commpr1 - 1];
			if (pat[commpr1] == '(')
				commpr1++;
		}
		int commpr2 = commpr;
		if (!used) {
			while (commpr2 > 0 && pat[commpr2] != ')')
				commpr2 = fail[commpr2 - 1];

			if (pat[commpr2] == ')')
				commpr2++;
		}

		int result = dp(i + 1, count + 1, commpr1);
		result += dp(i + 1, count - 1, commpr2);

		return memo[i][count][commpr] = result % MOD;

	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		len = 2 * sc.nextInt();
		s = sc.next();
		sub = s.length();
		pat = s.toCharArray();
		memo = new int[len][len][sub + 1];
		pattern();
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				for (int k = 0; k <= sub; k++)
					memo[i][j][k] = -1;
			}
		}
		out.println(dp(0, 0, 0));
		out.flush();
		out.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

}
