DP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll p=1e9;
ll f[310][310];
int main()
{
	string s;cin>>s;
	int n=s.size();s=' '+s;
	for(int i=1;i<=n;i++)f[i][i]=1;
	for(int l=2;l<=n;l++)
		for(int i=1;i+l-1<=n;i++)
		{
			int j=i+l-1;
			for(int k=i;k<=j;k++)if(s[i]==s[k])
				f[i][j]=(f[i][j]+f[i+1][k-1]*f[k][j])%p;
		}
	cout<<f[1][n];
}