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 <iostream>
#include <string>
#include <algorithm>

typedef long long int ll;

const ll MOD=ll(1e9)+7;

ll fat[6666];
ll ifat[6666];

ll fexp(ll a, int e)
{
	ll ans=1;
	while(e)
	{
		if(e&1)
			ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		e=e>>1;
	}
	return ans;
}

std::string str;
int n, m;

ll memo[2020][2020];
bool visit[2020][2020];

ll pd(int size, int op)
{
	//std::cout << "on pd(" << size << ',' << op << ")\n";
	if(op<0 || op>size)
		return 0;
	if(size==1)
	{
		if(op==1)
			return 1;
		else
			return 0;
	}
	if(size==0)
		return 1;
	ll &ans=memo[size][op];
	if(visit[size][op])
		return ans;
	visit[size][op]=true;
	return ans=(pd(size-1,op) + pd(size-1,op-1))%MOD;
}

int main()
{
	std::cin >> n >> m >> str;
	fat[0]=ifat[0]=1;
	for(int i=1;i<6666;i++)
	{
		fat[i]=(fat[i-1]*i)%MOD;
		ifat[i]=fexp(fat[i],MOD-2);
	}
	int diff=0;
	int op=0;
	int close=0;
	for(int i=0;i<m;i++)
	{
		if(str[i]=='(')
			op++;
		else
			close++;
		diff=std::min(diff,op-close);
	}
	if(op>n/2 || close>n/2 || n&1)
	{
		std::cout << "0\n";
		return 0;
	}
	if(n==m)
	{
		std::cout << "1\n";
		return 0;
	}
	int limit=n-m-std::max(0,op-close);
	ll ans=0;
	//std::cout << "?\n";
	for(int i=-diff;i<n-m;i++)
	{
		for(int j=-diff;j<=i;j++)
		{
			int cur_op=n/2-(op+j);
			if(op+j>n/2) break;
			int cur_end=close+(i-j);
			if(cur_end>n/2) break;
			int end_size=n-m-i;
			ll comb=(fat[end_size]*ifat[cur_op])%MOD;
			comb=(comb*ifat[end_size-cur_op])%MOD;
			ll nxt=(pd(i,j)*comb)%MOD;
			ans=(ans+nxt)%MOD;
			//std::cout << "found " << nxt << " on prefix size " << i << " using " << j << "'('\n";

		}
	}
	std::cout << ans << '\n';

}