/*
1. 状态定义：f[i][j] 为i~j的序列对应可能的树的集合
2. 状态计算：用最后一棵以k为根节点的子树划分整个集合 f[i][j] += (f[i][k] * f[k+1][j-1])

3. 边界：
    初始化：f[~][~] = 0, f[i][i] = 1 

4. 本题偶数是非法的，因为序列数size 与树节点树n的关系是： size = 1 + 2*(n-1) = 2n -1 

*/

import java.util.*;

public class Main{

    void run(){
        char[] str = jin.next().toCharArray();
        int n = str.length;
        if (n % 2 == 0){
            System.out.println(0);
            return ;
        }

        for (int i = 0 ; i <= n ; i++){
            for (int j = 0 ; j <= n ;j ++){
                if (i == j) f[i][j] = 1;
            }
        }

        for (int len = 1 ; len <= n; len+=2){
            // for (int i = 0 ; i + len - 1 < n ; i += 2){ 因为每一个起点都有可能是一个子树所以i++
            for (int i = 0 ; i + len - 1 < n ; i ++){
                int j = i + len -1;
                for (int k = i ; k < j ; k += 2){
                    if (str[k] == str[j]) f[i][j] = (f[i][j] + (f[i][k] * f[k+1][j-1]) % mod) % mod;
                }
            }
        }

        System.out.println(f[0][n-1]);
    }

    int maxN = 302;
    long mod = 1000000000;
    long[][] f = new long[maxN][maxN];
    Scanner jin = new Scanner(System.in);
    public static void main(String[] args){new Main().run();}
}