1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(regitser int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int p=1e9+7;
const int N=800;
ll dp[N][N][3][3],ans;
int mach[N],tmp[N],n,cnt;
char str[N+1];
inline void (){
scanf("%s",str+1);n=strlen(str+1);
rep(i,1,n)if(str[i]=='(')tmp[++cnt]=i;else if(str[i]==')')mach[tmp[cnt--]]=i;
}
ll dfs(int l,int r){
if(r==l+1)return dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
if(mach[l]==r){
dfs(l+1,r-1);
rep(i,0,2)rep(j,0,2){
if(j!=1)dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%p;
if(j!=2)dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%p;
if(i!=1)dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%p;
if(i!=2)dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%p;
}
}
else {
dfs(l,mach[l]);
dfs(mach[l]+1,r);
rep(i,0,2)rep(j,0,2)rep(x,0,2)rep(y,0,2){
if(x&&x==y)continue;
dp[l][r][i][j]=(dp[l][r][i][j]+dp[l][mach[l]][i][x]*dp[mach[l]+1][r][y][j]%p)%p;
}
}
}
int main(){
init();
dfs(1,n);
rep(i,0,2)rep(j,0,2)ans=(ans+dp[1][n][i][j])%p;
printf("%dn",ans);
return 0;
}
|
近期评论