Once Petya read a PRoblem about a bracket sequence. He gave it much thought but didn't find a solution. Today you will face it.

You are given string s. It represents a correct bracket sequence. A correct bracket sequence is the sequence of opening ("(") and closing (")") brackets, such that it is possible to obtain a correct mathematical expression from it, inserting numbers and Operators between the brackets. For example, such sequences as "(())()" and "()" are correct bracket sequences and such sequences as ")()" and "(()" are not.

In a correct bracket sequence each bracket corresponds to the matching bracket (an opening bracket corresponds to the matching closing bracket and vice versa). For example, in a bracket sequence shown of the figure below, the third bracket corresponds to the matching sixth one and the fifth bracket corresponds to the fourth one.

You are allowed to color some brackets in the bracket sequence so as all three conditions are fulfilled:

Find the number of different ways to color the bracket sequence. The ways should meet the above-given conditions. Two ways of coloring are considered different if they differ in the color of at least one bracket. As the result can be quite large, print it modulo1000000007 (109?+?7).

The first line contains the single string s (2?≤?|s|?≤?700) which represents a correct bracket sequence.

Print the only number — the number of ways to color the bracket sequence that meet the above given conditions modulo 1000000007(109?+?7).

(())output
12input
(()())output
40input
()output
4Note
Let's consider the first sample test. The bracket sequence from the sample can be colored, for example, as is shown on two figures below.
The two ways of coloring shown below are incorrect.
題目描述：
　　給一個合法的括號串，然后問這串括號有多少種涂色方案，當然啦！涂色是有限制的。
　　1,每個括號只有三種選擇：涂紅色，涂藍色，不涂色。
　　2,每對括號有且僅有其中一個被涂色。
　　3,相鄰的括號不能涂相同的顏色，但是相鄰的括號可以同時不涂色。
解題思路：
給出的括號序列，括號的匹配都是固定的，也就是說只需要給這些固定匹配的括號按照上面限制涂色就好啦。
　　可以定義 dp[l][r][x][y] 表示區間 [l, r] 在左端點涂x色，右端點涂y色的情況下的方案數。其中0代表不涂色， 1代表涂紅色， 2代表涂藍色。
　　窩們可以把括號序列可以分為兩類分別進行狀態轉移：
　　括號套括號，狀態轉移是：dp[l][r][x][y] += dp[l+1][r-1][x'][y'] (0<=x'<3, x'!=x, 0<=y'<3, y!=y')
　　多個匹配串連起來，轉臺轉移是：dp[l][r][x][y] += dp[l][nu][x'][y'] * dp[nu][r][x''][y''] (nu是l對應的另一邊括號)
　　當l+1 == r的時候有：dp[l][r][0][1] = 1;　　dp[l][r][1][0] = 1;
　　　　　　　　　　　　 dp[l][r][0][2] = 1;　　dp[l][r][2][0] = 1;
細節：
如果l+1 == r 說明最里面那1對，一共就只有4種情況，同理如果兩個括號相相匹也有4中情況，這就是為什么 這兩種情況詳細寫出左右括號顏色的原因，一開始糾結為什么第三種情況不用考慮，直接枚舉顏色就好了，萬一兩個一樣的呢。。。 注意 第三種是不匹配的，所以根本不用管i，j是不是可能相同，因為可能是這種的（）（），然后dfs分別求出dp[l][k]，dp[k+1][r]所有可能，dp[l][k]肯定是匹配的所以他下層dfs肯定是進入第二種或者第一種情況，dp[k+1][r]卻不一定是匹配的
這種遞歸的在區間dp里很常見，有深刻理解下，另一個遞歸的題目：
http://blog.csdn.net/QQ_34374664/article/details/59483996
深刻理解下遞歸
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int Mod = 1e9 + 7;const int maxn = 750;long long dp[maxn][maxn][5][5], temp[maxn], match[maxn];int len;char str[maxn];void get_match()  //這里就是最簡單的括號匹配問題，用兩個數組記錄下，p作為“棧頂”{    len = strlen(str);    int p = 0;    for(int i = 0; i < len; i++)    {        if(str[i] == '(')            temp[p++] = i;        else        {            match[i] = temp[p-1];            match[temp[p-1]] = i;            p--;        }    }}void dfs(int l, int r){    if(l+1 == r)    {        dp[l][r][0][1] = 1;        dp[l][r][1][0] = 1;        dp[l][r][0][2] = 1;        dp[l][r][2][0] = 1;        return ;    }    if(match[l] == r)    {        dfs(l+1, r-1);        for(int i = 0; i < 3; i++)            for(int j = 0; j < 3; j++)  //這兩個括號是匹配的，所以他的兩個括號不能同時染色，其實也就是4種情況了，一一枚舉            {                if(i != 1)                    dp[l][r][1][0] = (dp[l][r][1][0]+dp[l+1][r-1][i][j])%Mod;                if(i != 2)                    dp[l][r][2][0] = (dp[l][r][2][0]+dp[l+1][r-1][i][j])%Mod;                if(j != 1)                    dp[l][r][0][1] = (dp[l][r][0][1]+dp[l+1][r-1][i][j])%Mod;                if(j != 2)                    dp[l][r][0][2] = (dp[l][r][0][2]+dp[l+1][r-1][i][j])%Mod;            }//        for(int i = 0; i < 3; i++)//            for(int j = 0; j < 3; j++)//                for(int x = 0; x < 3; x++)//                    for(int y = 0; y < 3; y++)//                    {//                        if(i && j) continue;//                        if(x == i && x) continue;//                        if(y == j && y) continue;//                        dp[l][r][i][j] = (dp[l][r][i][j] + dp[l+1][r-1][x][y])%Mod;//                    }    }    else    {        int k = match[l];        dfs(l, k);        dfs(k+1, r);        for(int i = 0; i < 3; i++)            for(int j = 0; j < 3; j++)                for(int x = 0; x < 3; x++)                    for(int y = 0; y < 3; y++)                    {                        if(x == y && x != 0) continue;                        dp[l][r][i][j] = (dp[l][r][i][j] + dp[l][k][i][x]*dp[k+1][r][y][j])%Mod;  //不匹配，括號顏色不必保證一個不染色，保證相鄰不重復就好了                    }    }}int main(){    scanf("%s", str);    get_match();    dfs(0, len-1);    long long ans = 0;    for(int i = 0; i < 3; i++)        for(int j = 0; j < 3; j++)        {            ans = (ans + dp[0][len-1][i][j]) % Mod;  //枚舉所有染色可能性，因為最開始的不一定左右匹配        }    printf("%lld/n", ans);    return 0;}