krsu 3358

/*
by:senb1
*/

#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <locale>
#include <map>
#include <numeric>
#include <stack>
#include <string>
#include <valarray>
#include <vector>
#include <assert.h>
#include <memory>
#include <stdio.h>

using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define yes cout<<"YES\n"
#define no cout<<"NO\n"

const int N = 5005;
const int mod = 29876543;

int n;
int dp[N][N];
string s;

void solve() {
    cin >> s;
    n = s.size();
    s = ' ' + s;

    for (int r = 1; r <= n; r++) {
        for (int l = r; l >= 1; l--) {
            if (l == r) {
                dp[l][r] = 1;
                continue;
            }
            dp[l][r] = (dp[l][r] + dp[l][r - 1]) % mod;
            dp[l][r] = (dp[l][r] + dp[l + 1][r]) % mod;
            dp[l][r] = (dp[l][r] - dp[l + 1][r - 1]) % mod;
            if (dp[l][r] < 0)
                dp[l][r] += mod;
            if (s[l] == s[r]) {
                dp[l][r] = (dp[l][r] + dp[l + 1][r - 1] + 1) % mod;
            }
        }
    }

    cout << dp[1][n] << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}