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; 1.  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 10<sup class="upper-index">9</sup> + 7.
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.
In the first sample there are four different valid pairs: 
 1.  *p* = "(", *q* = "))" 1.  *p* = "()", *q* = ")" 1.  *p* = "", *q* = "())" 1.  *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.
4 1
(
4
4 4
(())
1
4 3
(((
0
875 50
)))((())()))((()(())))))())))((((((()))))))()(((((
0
1980 464
))(()()))(((((((((()))))))(()(((()((()))()()())()))()))(()))))))(())((())))()())()((())())()())))(())()(()))(()())()((((()))())()(())))))(()()(()(((((()(()()))(((()))(())))))()())(())))))())()()((())))))))((()(())))))()()(()((()((()()))(()))(())(()))()((((())()()))))))()(())))()(()())()())(((((()))())))())())(()))()(()))())((())((((()(()(())))(((()()))))()()()))))((()())()((())())))())))()(()(()()(((((()((((()))()(())()))))()(()))(()(((((((()((()(())))(((((())
854368836
1542 282
())())()((()(()))()((())()))((())(()))))(()()))(())((()))()((()())())()))((())(((()(())((()()())((((())))((()((((()(()()))))(()(()()(())()((())())())))))()()())))(()((((()))(()(()(()(()))())((()()()()(()(()))())(((()(())()(())()()())))()))())(()))(((())()))((())()(())))))(())))()()
631927032
2 2
)(
0
2 2
))
0
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long long catalan[2001];

void catalanDP(int n)
{
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++)
    {
        catalan[i] = 0;
        for (int j=0; j<i; j++)
        {
            catalan[i] =(catalan[i]+ ((catalan[j] * catalan[i-j-1])%MOD))%MOD;
        }
    }
 }

int main()
{
	int n,m;
	string s;
	scanf("%d %d",&n,&m);
	cin>>s;
	int open=0;
	int clos=0;
	catalanDP(2001);
	long long ans=0;
	/*for(int i=0;i<=2000;i++)
	{
		printf("%lld ",catalan[i]);	
	}*/
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='(')
		{
			open++;
		}
		else
		{
			clos++;
		}
	}	
	int tba=(n-m);
	if(open==clos)
	{
		if(tba%2==1)
		{
			printf("0");
		}
		else
		{
			for(int i=0;i<=tba;i+=2)
			{
				ans+=(catalan[i]*catalan[tba-i])%MOD;
			}
			printf("%lld",ans);
		}
		//ans+=catalan[tba];
	}
	else if(clos>open)
	{
		int diff=(clos-open);
		if(tba<diff||((tba-diff)%2==1))
		{
			printf("0");
		}
		else
		{
			for(int i=0;i<=(tba-diff);i+=2)
			{
				ans+=(catalan[i]*catalan[tba-diff-i])%MOD;				
			}
			printf("%lld",ans);
			//ans=(ans+catalan[tba-diff])%MOD;
		}
	}
	else
	{
		int diff=(open-clos);
		if(tba<diff||((tba-diff)%2==1))
		{
			printf("0");
		}
		else
		{
			for(int i=0;i<=(tba-diff);i+=2)
			{
				ans+=(catalan[i]*catalan[tba-diff-i])%MOD;				
			}
			//ans=(ans+catalan[tba-diff])%MOD;
			printf("%lld",ans);
		}
	}
}