#include <bits/stdc++.h>
using namespace std;

const int p = 1e9; 
const int N = 1010;

char s[N];
long long f[N][N];

int main(){
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout); 
	cin>>(s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++){
		f[i][i]=1;
	}
	for(int len=2;len<=n;len++){
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			if(s[i]!=s[j])continue;
			for(int k=i;k<j;k++){
				f[i][j]=max(f[i][j],f[i][j]+(s[i]==s[k])*f[i][k]*f[k+1][j-1]%p)%p;
			} 
		}
	}
	printf("%lld",f[1][n]);
	return 0;
}