CF gym 总是 wa6，感觉是个很明显的错误但是死活看不出来。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=305;
const int mod=1e9;
ll n,f[maxn][maxn],len;
char s[maxn];
ll dfs(ll l, ll r) {
    if(f[l][r]>0) {
        return f[l][r];
    }
    if(s[l]!=s[r]) {
        return 0;
    }
    ll ret=dfs(l+1,r-1);
    for(int k=l+2;k<=r-2;k++) {
        if(s[k]==s[l]) {
            ret=(ret+(dfs(l+1,k-1)*dfs(k,r))%mod)%mod;
        }
    }
    f[l][r]=ret;
//    cout<<l<<" "<<r<<" "<<ret<<endl;
    return ret;
}
int main() {
//    freopen("exploring.in","r",stdin);
//    freopen("exploring.out","w",stdout);
    scanf("%s",s+1);
    len=strlen(s+1);
    for(int i=1;i<=len;i++) {
        f[i][i]=1;
    }
    cout<<dfs(1,len)<<endl;
    return 0;
}