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;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define mp make_pair

const int N=3228;
const int MOD=1000*1000*1000+7;

ll more[N][N];

void precalc(){
    more[0][0]=1;
    for(int i=1;i<N;++i){
        for(int j=0;j<N;++j){
            if(j>0)
                more[i][j] += more[i-1][j-1];
            if(j<N-1)
                more[i][j] += more[i-1][j+1];
            more[i][j] %= MOD;
        }
    }
}

void solve(){
    precalc();
    int n,m;
    int minn=0,maxx=0,delta=0;
    cin>>n>>m;
    for(int i=0;i<m;++i){
        char cur;
        cin>>cur;
        if(cur=='(')
            delta += 1;
        else
            delta -= 1;
        minn = min(minn,delta);
        maxx = max(maxx,delta);
    }
    minn *= -1;
   // cout<<minn<<"  "<<maxx<<endl;
  /*  for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cout<<more[i][j]<<"  ";
        }
        cout<<endl;
    }*/
    ll ans=0;
    for(int p=0;p<=n-m;++p){
        for(int j=minn;j<=p;++j){
            ll cur1=more[p][j];
            if( delta+j<0 || delta+j>=N )
                continue;
            ll cur2=more[n-m-p][delta+j];
            ans+=((cur1*cur2)%MOD);
            ans %= MOD;
        }
    }
    cout<<ans<<endl;
}





int main(){
    double tt=clock();
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
    #endif // LOCAL
    ios_base::sync_with_stdio(false);
    //cout<<setprecision(20);
    //cout<<fixed;
    solve();
    #ifdef LOCAL
        cout<<"Time: "<<((ld)clock()-tt)/CLOCKS_PER_SEC<<endl;
    #endif // LOCAL
    return 0;
}
