/*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int mod=1e9;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 char s[mxn];

 int f[mxn][mxn];

 int main(){

     int i,j;

     while(scanf("%s",s+)!=EOF){

         int n=strlen(s+);

         memset(f,,sizeof f);

         for(i=;i<=n;i++)f[i][i]=;

         for(int st=;st<=n;st++){

             for(i=;i<=n;i++){

                 j=i+st-;if(j>n)break;

                 if(s[i]==s[j]){

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

                         if(s[k]==s[i]){

                             f[i][j]=((long long)f[i][j]+((long long)f[i+][k-]*f[k][j])%mod)%mod;

                         }

                     }

                 }

             }

         }

         printf("%d\n",f[][n]);

     }

     return ;

 }