CountPal

#include <iostream>
#include <cstring>
#define M 777013
using namespace std;
char s[5001];
int dp[5001];

bool pal(int a,int b)
{
    --a,--b;
    while(a<b&&s[a]==s[b])
        ++a,--b;
    if(a>=b)
        return true;
    return false;
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.getline(s,5001);
    int n=strlen(s);
    dp[0]=1;
    for(int i=1;i<=n;++i)
    {
        dp[i]+=dp[i-1],dp[i]%=M;
        for(int j=1;j<i;++j)
            if(pal(j,i))
                dp[i]+=dp[j-1],dp[i]%=M;
    }
    cout<<dp[n];
    return 0;
}