#include<bits/stdc++.h>

#define LL long long

#define LD long double

#define ull unsigned long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ALL(x) (x).begin(), (x).end()

#define fio ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}

template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < ) a += mod;}

template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}

template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;}

struct Ac {

    int ch[N][], f[N], tot, sz;

    int n, tar, dp[N][N][N][];

    char s[N];

    inline int newNode() {

        tot++; f[tot] = ;

        memset(ch[tot], , sizeof(ch[tot]));

        return tot;

    }

    void init(int _sz) {sz = _sz; tot = -; newNode();}

    inline int idx(int c) {return c - '(';}

    void addStr(char* s) {

        int u = ;

        for(int i = ; s[i]; i++) {

            int c = idx(s[i]);

            if(!ch[u][c]) ch[u][c] = newNode();

            u = ch[u][c];

        }

        tar = u;

    }

    void build() {

        queue<int> que;

        for(int c = ; c < sz; c++) {

            int v = ch[][c];

            if(!v) ch[][c] = ;

            else f[v] = , que.push(v);

        }

        while(!que.empty()) {

            int u = que.front(); que.pop();

            for(int c = ; c < sz; c++) {

                int v = ch[u][c];

                if(!v) ch[u][c] = ch[f[u]][c];

                else f[v] = ch[f[u]][c], que.push(v);

            }

        }

    }

    void solve() {

        init();

        scanf("%d", &n);

        scanf("%s", s);

        addStr(s);

        build();

        dp[][][][] = ;

        for(int i = ; i <  * n; i++) {

            for(int u = ; u <= tot; u++) {

                for(int c = ; c <= n; c++) {

                    for(int p = ; p < ; p++) {

                        if(!dp[i][u][c]) continue;

                        if(c <= n) {

                            int v = ch[u][];

                            add(dp[i + ][v][c + ][p || v == tar], dp[i][u][c][p]);

                        }

                        if(i - c < c) {

                            int v = ch[u][];

                            add(dp[i + ][v][c][p || v == tar], dp[i][u][c][p]);

                        }

                    }

                }

            }

        }

        int ans = ;

        for(int u = ; u <= tot; u++)

            add(ans, dp[ * n][u][n][]);

        printf("%d\n", ans);

    }

} ac;

int main() {

    ac.solve();

    return ;

}

/*

*/