CF149D

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;
const int N=705;

inline void add(int &a,const int &b){
    if((a+=b)>=p)a-=p;
}

int a[N];
int f[N][N][3][3];

void dfs(int l,int r){
    if(r==l+1){
        f[l][r][0][1]=1;
        f[l][r][0][2]=1;
        f[l][r][1][0]=1;
        f[l][r][2][0]=1;
        return ;
    }
    if(a[l]==r){
        dfs(l+1,r-1);
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                for(int k=1;k<3;++k){
                    if(i^k)add(f[l][r][k][0],f[l+1][r-1][i][j]);
                    if(j^k)add(f[l][r][0][k],f[l+1][r-1][i][j]);
                }
            }
        }
    }
    else {
        dfs(l,a[l]);
        dfs(a[l]+1,r);
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                for(int k=0;k<3;++k){
                    for(int m=0;m<3;++m){
                        if(j==k && j)continue;
                        add(f[l][r][i][m],(ll)f[l][a[l]][i][j]*f[a[l]+1][r][k][m]%p);
                    }
                }
            }
        }
    }
}

char s[N];
int sta[N],tot;

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;++i){
        if(s[i]=='('){
            sta[++tot]=i;
        }
        else {
            a[sta[tot]]=i;
            a[i]=sta[tot];
            --tot;
        }
    }
    dfs(0,n-1);
    int ans=0;
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            add(ans,f[0][n-1][i][j]);
    printf("%d\n",ans);
    return 0;
}