#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include <math.h>using namespace std;typedef long long LL;const LL mod = 1000000000;const LL maxn = 300 + 10;LL dp[maxn][maxn];char s[maxn];LL gao(LL i, LL j){    if (~dp[i][j]) return dp[i][j];    if (i == j) return dp[i][j] = 1;    if (s[i] != s[j]) return dp[i][j] = 0;    LL ans = 0;    for (LL x = i + 2; x <= j; x++){        if (s[i] != s[x]) continue;        ans += gao(i + 1, x - 1) * gao(x, j);        ans %= mod;    }    return dp[i][j] = ans;}int main(){    while (cin >> s){        LL len = strlen(s);        memset(dp, -1, sizeof(dp));        cout << gao(0, len - 1)<<endl;    }    return 0;}