#include<bits/stdc++.h>
using namespace std;
string s;
long long n,dp[305][305];
long long f(long long l,long long r){
    if(l>r) return dp[l][r]=0;
    if(l==r) return dp[l][r]=1;
    if(dp[l][r]>-1) return dp[l][r];
    if(s[l]!=s[r]) return dp[l][r]=0;
    dp[l][r]=0;
    for(int i=l;i<=r;i++){
        if(s[l]==s[i]){
            dp[l][r]+=f(l+1,i-1)*f(i,r);
            dp[l][r]%=1000000000;
        }
    }
    return dp[l][r]%=1000000000;
}
int main(){
    freopen("ZYH.in","r",stdin);
    freopen("ZYH.out","w",stdout);
    cin>>s;
    n=s.length();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            dp[i][j]=-1;
        }
    }
    cout<<f(0,n-1);
	return 0;
}