易错点：

• 题目给出的是欧拉序，也就是每个点的颜色不重复。因此，就可以利用相同颜色的点作为一个阶段进行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\n",dfs(1,n)%mod);
    return 0;
}