149D - Coloring Brackets - CodeForces Solution

// Problem: D. Coloring Brackets
// Contest: Codeforces - Codeforces Round 106 (Div. 2)
// URL: https://codeforces.com/problemset/problem/149/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
#define remake return
#define fastio do{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}while(0)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define udm unordered_map<int,int>
typedef complex<double> cp;
#define int long long
#define rd(x) scanf("%lld",&x)
#define FOR(i,x,y) for(auto i=(x);i<=(y);i++)
#define ROF(i,x,y) for(auto i=(x);i>=(y);i--)
#define mem(x) memset(&x,0,sizeof x)
#define INF (1ll<<62)
#define endl '\n'


const int N = 2e5+5;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

void pre(){
	return;
}
int dp[701][701][3][3];
int rr[701];
int n;

void dfs(int l,int r){
	if(r==l+1){
		dp[l][r][0][1]=1;
		dp[l][r][0][2]=1;
		dp[l][r][1][0]=1;
		dp[l][r][2][0]=1;
		return;
	}
	if(rr[l]==r){
		dfs(l+1,r-1);
		for(int i=0;i<=2;i++){
			for(int j=0;j<=2;j++){
				if(j!=1) dp[l][r][0][1]+=dp[l+1][r-1][i][j];
				if(j!=2) dp[l][r][0][2]+=dp[l+1][r-1][i][j];
				if(i!=1) dp[l][r][1][0]+=dp[l+1][r-1][i][j];
				if(i!=2) dp[l][r][2][0]+=dp[l+1][r-1][i][j];
				dp[l][r][0][1]%=MOD;
				dp[l][r][0][2]%=MOD;
				dp[l][r][1][0]%=MOD;
				dp[l][r][2][0]%=MOD;
			}
		}
	}else{
		dfs(l,rr[l]);
		dfs(rr[l]+1,r);
		FOR(i,0,2)
		FOR(j,0,2)
		FOR(p,0,2)
		FOR(q,0,2){
			if((j==1&&p==1)||(j==2&&p==2)) continue;
			dp[l][r][i][q]+=(dp[l][rr[l]][i][j] * dp[rr[l]+1][r][p][q])%MOD;
			dp[l][r][i][q]%=MOD;
		}
	}
}

void solve(){
	string str;
	cin>>str;
	stack<int> s;
	n = (int)str.size();
	
	for(int i=1;i<=n;i++){
		if(str[i-1]=='(') s.push(i);
		else{
			rr[s.top()]=i;
			rr[i]=s.top();
			s.pop();
		}
	}
	dfs(1,n);
	int ans=0;
	FOR(i,0,2)
	FOR(j,0,2){
		ans+=dp[1][n][i][j];
		ans%=MOD;
	}
	cout<<ans;
	return;
}
signed main(){
	pre();
	int T=1;
	// rd(T);
	while(T--){
		solve();
	}
	return 0;
}