#include<bits/stdc++.h>
#define int long long
using namespace std;
auto IN = freopen("ZYH.in", "r", stdin);
auto OUT = freopen("ZYH.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 305, MOD = 1e9;
int f[N][N], n, g[N];
char s[N];
signed main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n; i ++){
        f[i][i] = 1;
    }
    for(int l = n - 1; l >= 1; l --){
        for(int k = 1; k <= n; k ++){
            g[k] = 0;
        }
        g[l] = 1;
        for(int k = l + 1; k <= n; k ++){
            if(s[k] == s[l]){
                for(int o = l; o < k; o ++){
                    if(s[o] == s[l]){
                        (g[k] += g[o] * f[o + 1][k - 1] % MOD) %= MOD;
                    }
                }
                f[l][k] = g[k];
            }
        }
    }
    printf("%lld", f[1][n]);
    return 0;
}