As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length n more than any other strings!

The sequence of round brackets is called valid if and only if: 

  1. the total number of opening brackets is equal to the total number of closing brackets; 
  2. for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets. 



Gabi bought a string s of length m (m ≤ n) and want to complete it to obtain a valid sequence of brackets of length n. He is going to pick some strings p and q consisting of round brackets and merge them in a string p + s + q, that is add the string p at the beginning of the string s and string q at the end of the string s.

Now he wonders, how many pairs of strings p and q exists, such that the string p + s + q is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 109 + 7.

Input

First line contains n and m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.

The second line contains string s of length m consisting of characters '(' and ')' only.

Output

Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.

Examples

Input

4 1
(


Output

4


Input

4 4
(())


Output

1


Input

4 3
(((


Output

0

Note

In the first sample there are four different valid pairs: 

  1. p = "(", q = "))" 
  2. p = "()", q = ")" 
  3. p = "", q = "())" 
  4. p = "", q = ")()" 



In the second sample the only way to obtain a desired string is choose empty p and q.

In the third sample there is no way to get a valid sequence of brackets.
import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.io.*;
import java.util.*;

public class C343C
{

private static StringTokenizer st;
    
    public static void nextLine(BufferedReader br) throws IOException
    {
        st = new StringTokenizer(br.readLine());
    }
    
    public static int nextInt()
    {
        return Integer.parseInt(st.nextToken());
    }
    
    public static String next()
    {
        return st.nextToken();
    }
    
    public static long nextLong()
    {
        return Long.parseLong(st.nextToken());
    }

    public static double nextDouble()
    {
        return Double.parseDouble(st.nextToken());
    }
    
    static long MOD = 1000000007;
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nextLine(br);
        int n = nextInt();
        int m = nextInt();
        nextLine(br);
        String s = next();
        int l = 0, r = 0;
        int min = 0, max = 0;
        for (int i = 0; i < m; i++)
        {
            if (s.charAt(i) == '(')
            {
                l++;
                max = Math.max(max, l - r);
            }
            else
            {
                r++;
                min = Math.min(min, l - r);
            }
        }
        if (n % 2 != 0)
        {
            System.out.println(0);
            return;
        }
        
        if (Math.abs(l - r) > n-m)
        {
            System.out.println(0);
            return;
        }
        min = -min;
        int vary = n-m;
        long total = 0;
        long[][][] dp = new long[2][vary+2][vary+2];
        dp[0][0][1] = 1;
        if (min == 0)
        {
            dp[1][0][l-r] = 1;
        }
        for (int i = 1; i < vary+1; i++)
        {
            dp[0][i][0] = dp[0][i-1][1];
            dp[1][i][0] = dp[1][i-1][1];
            if (r - l >= 0 && min <= r-l)
            {
                dp[1][i][0] = moda(dp[1][i][0], dp[0][i-1][r-l], MOD);
            }
            for (int j = 1; j < vary+1; j++)
            {
                dp[0][i][j] = moda(dp[0][i-1][j-1], dp[0][i-1][j+1], MOD);
                dp[1][i][j] = moda(dp[1][i-1][j-1], dp[1][i-1][j+1], MOD);
                int pos = j + (r - l);
                if (pos >= min && pos <= vary)
                {
                    dp[1][i][j] = moda(dp[1][i][j], dp[0][i-1][pos], MOD);
                }
            }
            
        }
        /*
        for (int i = 0; i <= vary; i++)
        {
            for (int k = 0; k < 2; k++)
            {
                for (int j = 0; j <= vary; j++)
                {
                    System.out.print(dp[i][j][k] + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
        */
        System.out.println(dp[1][vary][0]);
        
    }
    
    
    private static long modexp(long a, long b, long m)
    {
        long k = 1;
        while (b > 0)
        {
            if ((b & 1) == 1)
            {
                k = modm(a, k, m);
            }
            b = b >> 1;
            a = modm(a, a, m);
        }
        return k;
    }
    
    private static long modinv(long a, long m)
    {
        return modexp(a, m-2, m);
    }
    
    private static long moda(long a, long b, long m)
    {
        return (a+b) % m;
    }
    
    private static long modm(long a, long b, long m)
    {
        return ((a % m)*(b % m)) % m;
    }
    
    public static long[] modfact;
    
    private static void genModFact(int n, long m)
    {
        modfact = new long[n+1];
        modfact[0] = modfact[1] = 1;
        for (int i = 2; i < n+1; i++)
        {
            modfact[i] = modm(modfact[i-1], i, m);
        }
    }
    
    private static long modchoose(int n, int k, long m)
    {
        long denom = modm(modfact[k], modfact[n-k], m);
        return modm(modfact[n], modinv(denom, m), m);
    }

    
}