Empty String

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;
const ll N = 500 + 9;

ll F[N], Inv[N], rangeDP[N][N];
string A;

ll Flex (ll);

ll bp (ll a, ll b) {
    if (b == 0)
        return 1;
    ll tmp = bp (a, b / 2);
    if (b & 1)
        return Flex (Flex (tmp * tmp) * a);
    return Flex (tmp * tmp);
}

ll C (ll n, ll m) {
    if (m > n)
        return 0;
    return Flex (F[n] * Flex (Inv[m] * Inv[n - m]));
}

ll Flex (ll x) {
    return (((x % MOD) + MOD) % MOD);
}

ll Go (ll l, ll r) {
    if (r < l)
        return 1;
    if (r == l + 1)
        return A[l] == A[r];
    if (l == r)
        return 0;
    if ((r - l + 1) & 1)
        return 0;
    if (rangeDP[l][r] != -1)
        return rangeDP[l][r];
    ll ret = 0;
    if (A[l] == A[r]) {
        ret += Go (l + 1, r - 1);
        ret %= MOD;
    }
    for (ll i = l + 1; i < r; i++) {
        if (A[l] == A[i]) {
            ret += Flex (Flex (Go (l + 1, i - 1) * Go (i + 1, r)) * C ((r - l + 1) / 2, (i - l + 1) / 2));
            ret %= MOD;
        }
    }
    return rangeDP[l][r] = ret;
}

int main () {
    string s;
    cin >> s;
    ll n = s.length();
    A = '#' + s;
    F[0] = 1;
    for (ll i = 1; i < N; i++)
        F[i] = Flex (F[i - 1] * i);
    Inv[N - 1] = bp (F[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        Inv[i] = Flex (Inv[i + 1] * (i + 1));
    memset (rangeDP, -1, sizeof (rangeDP));
    cout << Go (1, n) << "\n";
    return 0;
}