#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9;
char ch[305];
int n,dp[305][305];
int dfs(int l,int r){
	if(l>r) return 0;
	if(l==r) return 1;
	if(ch[l]!=ch[r]) return 0;
	if(dp[l][r]) return dp[l][r];
	for(int k=l+2;k<=r;k++) dp[l][r]=(dp[l][r]+dfs(l+1,k-1)*dfs(k,r))%mod;
	return dp[l][r];
}
signed main(){
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.in","w",stdout);
	cin>>(ch+1); n=strlen(ch+1);
	for(int i=1;i<=n;i++){
		if(ch[i]!=ch[1]) dp[i][i]=1;
	}
	printf("%lld",dfs(1,n));
	return 0;
}