#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long mod=1e9;
char str[310];
int n;
long long f[310][310];
int main()
{
    freopen("ZYH.in","r",stdin);
    freopen("ZYH.out","w",stdout);
    scanf("%s",str+1);
    n=strlen(str+1);
    if(n%2==0)
    {
        printf("0");
        return 0;
    }  
    for(int len=1;len<=n;len+=2)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            if(len==1) f[l][r]=1;
            else 
            {
                if(str[l]==str[r])
                {
                    for(int k=l;k<r;k+=2)
                    {
                        if(str[k]==str[r]) f[l][r]=(f[l][r]+f[l][k]*f[k+1][r-1]%mod)%mod;
                    }
                }
            }
        }
    }   
    printf("%lld",f[1][n]);
    return 0;
}