CF149D Coloring Brackets

#include<bits/stdc++.h>
using namespace std;
#define int long long
class solve{
	public:
		char s[777];
		int f[1000][1000][3][3];
		int mod;
		int others[1000];
		void dfs(int x,int y){
			if(x+1==y){
				f[x][y][0][1]=f[x][y][0][2]=f[x][y][1][0]=f[x][y][2][0]=1;
				return;
			}
			if(others[y]==x){
				dfs(x+1,y-1);
				for(int i=0; i<=2; i++){
					for(int j=0; j<=2; j++){
						if(j!=1)
						f[x][y][0][1]=(f[x][y][0][1]+f[x+1][y-1][i][j])%mod;
						if(j!=2)
						f[x][y][0][2]=(f[x][y][0][2]+f[x+1][y-1][i][j])%mod;
						if(i!=1)
						f[x][y][1][0]=(f[x][y][1][0]+f[x+1][y-1][i][j])%mod;
						if(i!=2)
						f[x][y][2][0]=(f[x][y][2][0]+f[x+1][y-1][i][j])%mod;
					}
				}
				return;
			}
			else{
				dfs(x,others[x]);
				dfs(others[x]+1,y);
				int z=others[x];
				for(int i=0; i<=2; i++)
				for(int j=0; j<=2; j++)
				for(int l=0; l<=2; l++)
				for(int r=0; r<=2; r++){
					if(j==l&&j!=0)continue;
					f[x][y][i][r]=(f[x][y][i][r]+f[x][z][i][j]*f[z+1][y][l][r]%mod)%mod; 
				}
				return;
			}
		}
		void main()
		{
			scanf("%s",s+1);
			int n=strlen(s+1);
			stack < pair < char , int > > st;
			for(int i=1; i<=n; i++){
				if(s[i]=='('){
					st.push(make_pair(s[i],i));
				}
				else{
					others[i]=st.top().second;
					others[st.top().second]=i;
					st.pop();
				}
			}
			mod=1000000007;
			dfs(1,n);
			int ans=0;
			for(int i=0; i<=2; i++)
			for(int j=0; j<=2; j++)
			{
				ans=(ans+f[1][n][i][j])%mod;
			}
			cout<<ans<<endl;
		}
}x;
signed main()
{
	x.main();
}