#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=300+5;

const ll mod=1e9;

char s[maxn];

ll d[maxn][maxn];

ll dp(int i,int j)

{

    if(i>j) return 0;

    if(d[i][j]!=-1) return d[i][j];

    if(s[i]!=s[j]) return d[i][j]=0;

    if(i==j) return d[i][j]=1;

    d[i][j]=0;

    for(int k=i;k<j;k++)

        d[i][j]=(d[i][j]+dp(i,k)*dp(k+1,j-1)%mod)%mod;

    return d[i][j];

}

int main()

{

    freopen("exploring.in","r",stdin);

    freopen("exploring.out","w",stdout);

    while(~scanf("%s",s))

    {

        memset(d,-1,sizeof(d));

        printf("%I64d\n",dp(0,strlen(s)-1));

    }

    return 0;

}