#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
typedef long long LL;
const int maxn = 300 + 8, HASH = 1000000007;
LL dp[maxn][maxn]; //主要是 有 (int)a*(int)b 的这个可能int溢出
string line;
/*
inline LL add(int a, int b)
{
    LL c = a + b;
    return c >= HASH ? c - HASH : c;
}
*/
LL dfs(int a, int b)
{
    LL& res = dp[a][b];
    if(res == -1){
        if(a == b){
            res = 1;
        }
        else{
            res = 0;
            //line[a] is not removed
            char goalbra = '\0';
            if(line[a] == '('){
                goalbra = ')';
            }
            else if(line[a] == '['){
                goalbra = ']';
            }
            if(goalbra != '\0'){
                for(int i = a + 1; i < b; i++){
                    if(line[i] == goalbra){
                        res = (res + dfs(a + 1, i)*dfs(i + 1, b)) % HASH;
                    }
                }
            }
            //line[a] is removed
            res = (res + dfs(a + 1, b)) % HASH;
        }
    }
    return res;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int n;

    scanf("%d", &n);
    cin>>line;
    memset(dp, 255, sizeof dp);
    //cout<<dp[0][0]<<endl;
    printf("%lld", dfs(0, n) - 1);//不能全部去掉，所有有个 [a,a) 不能return 1 故这里 subtract 1 to find the wanted answer

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx