#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 310;
const ll mod = 1e9;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n;
char c[N];
ll f[N][N];
ll dfs(int l,int r){
	if(l == r)return 1;
	if(c[l] != c[r] || l > r)return 0;
	if(f[l][r] != -1)return f[l][r];
	ll ans = dfs(l+1,r-1);
	for(int k = l+2;k < r;k++)(ans += dfs(l+1,k-1) * dfs(k,r) % mod) %= mod;
//	cout<<' '<<l<<' '<<r<<' '<<ans<<"___________\n";
	return f[l][r] = ans;
}

int main(){
	freopen("ZYH.in","r",stdin);
	freopen("ZYH.out","w",stdout);
	cin>>(c + 1);
	n = strlen(c + 1);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)f[i][j] = -1;
//	dfs(3,5);
	printf("%lld\n",dfs(1,n));

	return 0;

}