#include<bits/stdc++.h>

 using namespace std;

 const int N = 1e6+;

 typedef long long ll;

 const int mod = 1e9+;

 int n,m,i,r,p,f[N<<]; char a[N],s[N<<];

 ll L[N], R[N];

 void add(ll& a, ll b){

     a += b;

     if(a >= mod||a <= -mod) a %= mod;

 }

 int main(){

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

         n = strlen(a+);

         for(i = ; i <= n; i++) s[i<<] = a[i], s[i<<|] = '#';

         s[] = '$', s[] = '#', s[m = (n+)<<] = '@';

         for(r=p=,f[]=,i=;i<m;i++){

             for(f[i]=r>i?min(r-i,f[p*-i]):;s[i-f[i]]==s[i+f[i]];f[i]++);

             if(i+f[i]>r)r=i+f[i],p=i;

         }

         memset(L, , sizeof(ll)*(n+));

         memset(R, , sizeof(ll)*(n+));

         for(i=;i<=*n; i++){

             int ret = f[i]-, pos = i/;

             if(ret == ) continue ;

             ret /= ;

             if(i&){

                 //[pos+1, pos+rer/2]

                 add(L[pos+], pos), add(L[pos+], --pos), add(L[pos+ret+], ret-pos), add(L[pos+ret+], pos+-ret);

                 //[pos-ret/2+1, pos]

                 add(R[pos-ret+], pos+ret), add(R[pos-ret+], --pos-ret), add(R[pos+], -pos), add(R[pos+], pos+);

             }else{

                 //[pos, pos+ret/2]

                 add(L[pos], pos), add(L[pos+], --pos), add(L[pos+ret+], ret-pos+), add(L[pos+ret+], pos-ret);

                 //[pos-ret/2, pos]

                 add(R[pos-ret], pos+ret), add(R[pos-ret+], --pos-ret), add(R[pos+], -pos), add(R[pos+], pos);

             }

         }

         for(i=; i<=n;i++)

             add(L[i], L[i-]), add(R[i], R[i-]);

         for(i=; i<=n;i++)

             add(L[i], L[i-]), add(R[i], R[i-]);

         ll ans = ;

         for(i=;i<n;i++){

             ans += L[i]*R[i+];

             if(ans >= mod||ans <= -mod)

                 ans %= mod;

         }

         cout << (ans+mod)%mod << endl;

     }

     return ;

 }