易错点：
- 题目给出的是欧拉序，也就是每个点的颜色不重复。因此，就可以利用相同颜色的点作为一个阶段进行dp.
- 因为需要模数，不能直接使用+=，即应当使用f[l][r]=(f[l][r]+dfs(l+1,k-1)*dfs(k,r)%mod)%mod.
- 划分点（k）可以从l开始，这是因为不合理的情况都被颜色剪枝了.
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN=350,mod=1e9;
char s[MAXN];
ll f[MAXN][MAXN];
ll dfs(int l,int r){
if(l==r)return 1;
if(s[l]!=s[r])return 0;
if(f[l][r]!=-1)return f[l][r];
f[l][r]=0;
for(int k=l+2;k<=r;k++){
f[l][r]=(f[l][r]+dfs(l+1,k-1)*dfs(k,r)%mod)%mod;
}
return f[l][r];
}
int main(){
memset(f,-1,sizeof(f));
scanf("%s",s+1);
int n=strlen(s+1);
printf("%lld
",dfs(1,n)%mod);
return 0;
}