当l = 38,r = 41时就一直卡在里面 样例:()()()((((())))())()()()()()((()))()()(())()(((())))()(()())((())())((()())(((((()()()())()()())))))

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
const long long MOD = 1000000007;
string x2;
int len;
stack <int> st;
long long f[705][705][3][3],sum;
int match[705];
int rev(int x1){
	if(x1 == 1) return 2;
	else return 1;
}
int dp(int l,int r,int x,int y){
    if(f[l][r][x][y] > -1) return f[l][r][x][y];
	if(l == r - 1){
		f[l][r][x][y] = ((x > 0) != (y > 0));
		return f[l][r][x][y];
	}
	f[l][r][x][y] = 0;
	if(r == match[l]){
		if((x && y) || (!x && !y)) return f[l][r][x][y] = 0;
		if(x == 0) return f[l][r][x][y] = (dp(l + 1,r - 1,1,0) + dp(l + 1,r - 1,2,0) + dp(l + 1,r - 1,0,0) + dp(l + 1,r - 1,0,rev(y)) + dp(l + 1,r - 1,1,rev(y)) + dp(l + 1,r - 1,2,rev(y))) % MOD;
		if(y == 0) return f[l][r][x][y] = (dp(l + 1,r - 1,0,1) + dp(l + 1,r - 1,0,2) + dp(l + 1,r - 1,0,0) + dp(l + 1,r - 1,rev(x),0) + dp(l + 1,r - 1,rev(x),1) + dp(l + 1,r - 1,rev(x),2)) % MOD;
	}
	else{
		for(int i = 0;i <= 2;i++)
			for(int j = 0;j <= 2;j++)
				f[l][r][i][j] = 0;
		for(int i = 0;i <= 2;i++)
			for(int j = 0;j <= 2;j++)
				for(int p = 0;p <= 2;p++)
					for(int q = 0;q <= 2;q++){
						if(j && p && (j == p)) continue;
						f[l][r][i][q] = (f[l][r][i][q] + dp(l,match[l],i,j) * dp(match[l] + 1,r,p,q) % MOD) % MOD;
					}
//		if(l == 38 && r == 41){
//			cout << f[l][r][x][y] << endl;
//		}
//		if(l == 42 && r == 99){
//			cout << f[l][r][x][y] << endl;
//		}
		return f[l][r][x][y];
	}
}
int main(){
	memset(f,-1,sizeof f);
	cin >> x2;
	len = x2.size();
	for(int i = 0;i < len;i++){
		if(x2[i] == '('){
			st.push(i);
		}
		else {
			int n = st.top();
			st.pop();
			match[n] = i;
		}
	}
	for(int i = 0;i <= 2;i++)
		for(int j = 0;j <= 2;j++)
			sum = (sum + dp(0,len - 1,i,j)) % MOD;
	cout << sum;
    return 0;
}