aca

aaaa

Sample Output

3

15
 

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define rep2(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int maxn=;

struct PAT

{

    struct node{

        int len,num,fail,son[];

    }t[maxn];

    int last,n,tot,s[maxn];

    void init()

    {

        memset(t,,sizeof(t));

        tot=last=; n=;

        t[].len=; t[].len=-;

        t[].fail=t[].fail=;

        s[]=-;

    }

    int add(int c){

        int p=last; s[++n]=c;

        while(s[n]!=s[n--t[p].len]) p=t[p].fail;

        if(!t[p].son[c]){

            int v=++tot,k=t[p].fail;

            while(s[n]!=s[n-t[k].len-]) k=t[k].fail;

            t[v].fail=t[k].son[c];

            t[v].len=t[p].len+;

            t[v].num=t[t[v].fail].num+;

            t[p].son[c]=v;

        }

        last=t[p].son[c];

        return t[last].num;

    }

}T;

ll ans,sum[maxn];char c[maxn];

int main()

{

    while(~scanf("%s",c+)){

        int N=strlen(c+);

        T.init(); ans=;

        rep(i,,N) sum[i]=sum[i-]+T.add(c[i]-'a');

        T.init();

        rep2(i,N,) ans+=sum[i-]*T.add(c[i]-'a');

        printf("%lld\n",ans);

    }

    return ;

}