对于括号问题，考虑区间 \(dp\)。这道题的括号序列是固定的，所以直接找出每个括号对应的括号在进行转化即可。
设 \(f_{l,r,0/1/2,0/1/2}\) 表示 \(l\sim r\)，左括号不染色/染红色/染蓝色，右括号不染色/染红色/染蓝色的方案数。
若 \(l,r\) 是一对匹配括号，那么f_{l,r} 便可以由 \(f_{l+1,r-1}\) 转移得来，注意相邻括号颜色不同。
接着进行中间的拆分，注意括号问题不能直接枚举断点 \(k\) 拆分，这样会将 \(()()()\) 分别拆成 \((),()()\) 和 \(()(),()\) 计算两次。所以强行规定第一个拆分的一定是左右括号匹配好的，后面一段不管，也就是将 \([l,r]\) 拆成 \([l,match_l]\) 和 \(match_l+1,r\) 两个区间进行计算，同样注意相邻括号颜色不能相同。
由于很大程度根据括号匹配情况进行 \(dp\)，所以这里采取记忆话搜索进行 \(dp\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define PII pair<int,int>
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=710;
const LL MOD=1e9+7;
int n; string s;
int match[N];
LL f[N][N][3][3];
int pd(int l,int r) {
if(s[l]=='('&&s[r]==')') return 1;
else return 0;
}
LL dfs(int l,int r,int p1,int p2) {
if(l>r) return 0;
if((r-l+1)%2!=0) return 0;
if(f[l][r][p1][p2]!=-1) return f[l][r][p1][p2];
f[l][r][p1][p2]=0;
if(match[l]==r) {
if((p1&&!p2)||(!p1&&p2)) {
for(int x1=0;x1<=2;x1++) {
for(int x2=0;x2<=2;x2++){
if((p1==x1&&x1)||(p2==x2&&x2)) continue;
f[l][r][p1][p2]=(f[l][r][p1][p2]+dfs(l+1,r-1,x1,x2))%MOD;
}
}
}
}
for(int x1=0;x1<=2;x1++) {
for(int x2=0;x2<=2;x2++){
if(x1==x2&&x1) continue;
f[l][r][p1][p2]=(f[l][r][p1][p2]+dfs(l,match[l],p1,x1)*dfs(match[l]+1,r,x2,p2))%MOD;
}
}
return f[l][r][p1][p2];
}
int main() {
cin>>s;
n=s.size(); s=" "+s;
stack<int> st;
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) {
if(st.size()&&s[st.top()]=='('&&s[i]==')') {
match[st.top()]=i; match[i]=st.top(); st.pop();
}
else st.push(i);
}
for(int i=1;i<=n-1;i++) {
if(pd(i,i+1)) {
f[i][i+1][0][1]=f[i][i+1][0][2]=f[i][i+1][1][0]=f[i][i+1][2][0]=1;
}
}
LL ans=0;
for(int i=0;i<=2;i++) {
for(int j=0;j<=2;j++) {
ans=(ans+dfs(1,n,i,j))%MOD;
}
}
cout<<ans<<endl;
return 0;
}