CodeForces 629C Famil Door and Brackets

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

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.

分析：先對給定的串做括号比對，然後求出剩下有l 個 ） 和 r 個 （,dp[i][j]表示長度為i的有效比對序列中多出j個左括号的方案數，那麼我們隻要枚舉p就能同時的到q.

#include <cstdio>
#include <iostream>
#define MAXN 1000000007
using namespace std;
int n,m,totl,totr;
char c;
long long dp[2005][2005],ans;
int main()
{
	scanf("%d %d",&n,&m);
	scanf("%c",&c);
	for(int i = 1;i <= m;i++) 
	{
		scanf("%c",&c);
		if(c == '(') totl++;
		else if(totl) totl--;
		     else totr++;
	}
	dp[0][0] = 1;
	for(int i = 1;i <= 2000;i++)
	{
		dp[i][0] = dp[i-1][1];
		for(int j = 1;j <= i;j++) 
		 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MAXN; 
	}
	for(int i = 0;i <= n - m;i++)
	 for(int j = totr;j <= i;j++)
	  if(j - totr + totl <= n - m - i) ans = (ans + dp[i][j]*dp[n - m - i][j - totr + totl]) % MAXN;
	cout<<ans<<endl;
}