//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;
const int N = 310, mod = 1e9;
int h[N][N];
string s;
inline int dfs(int l, int r)
{
    if (l == r) return 1;
    if (l > r) return 0;
    if (h[l][r] != -1) return h[l][r];
    h[l][r] = 0;
    for (int k = l + 2; k <= r; k ++ )
        if (s[k] == s[l])
            h[l][r] = (h[l][r] + (long long)dfs(l + 1, k - 1) * dfs(k, r)) % mod;
    return h[l][r];    
}
inline void solve()
{
    memset(h, -1, sizeof h);
    cin >> s;
    cout << dfs(0, s.size() - 1) << endl;
}
int main()
{
    solve();
    return 0;
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~