#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000000
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
string c;
vector <int> vec[1010];
ll dp[1010][1010],len;
ll ef(ll ch,ll id){
	ll l=0,r=vec[ch].size()-1;
	while(l<r){
//		cout<<l<<" "<<r<<endl;
		ll mid=(l+r)/2;
		if(vec[ch][mid]<id)l=mid+1;
		else r=mid;
	}
	return l;
}
void dfs(ll l,ll r){
	if((r-l)%2==1)return;
	if(dp[l][r]>0)return;
	if(l==r){
		dp[l][r]=1;
		return;
	}
	ll ch=c[l]-'A'+1;
	for(int i=ef(c[l],l)+1;i<vec[ch].size();i++){
		int y=vec[ch][i];
		if(y>=r)break;
		if((y-l)%2==1||c[y+1]!=c[r-1]||y<=l||(r-y)%2==1)continue;
		if(!dp[l][y])dfs(l,y);
		if(!dp[y+1][r-1])dfs(y+1,r-1);
//		cout<<l<<" "<<y<<" "<<r<<" "<<dp[l][y]<<" "<<dp[y+1][r-1]<<" ";
		dp[l][r]=(dp[l][r]+dp[l][y]*dp[y+1][r-1]%mod)%mod;
//		cout<<dp[l][r]<<endl;
	}
	if(c[l+1]!=c[r-1])return;
	if(!dp[l+1][r-1])dfs(l+1,r-1);
	dp[l][r]=(dp[l][r]+dp[l+1][r-1])%mod;
//	cout<<l<<" "<<r<<" "<<dp[l][r]<<endl;
}
int main(){
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout);
	cin>>c;
	len=c.length();
	c="0"+c;
//	cout<<c;
	for(int i=1;i<=len;i++)vec[c[i]-'A'+1].push_back(i);
//	for(int i=1;i<=26;i++){
//		for(int j=0;j<vec[i].size();j++)cout<<vec[i][j]<<" ";
//		cout<<endl;
//	}
	dfs(1,len);
	cout<<dp[1][len]%mod;
	return 0;
}