#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- struct PalindromicTree { struct node { map next; int len, sufflink,num,first; }; string S; vector V; int n,s; // num,suff bool add(int pos) { char ch=S[pos]; int c=s, cl=0; while(1) { cl=V[c].len; if(pos-1-cl>=0 && S[pos-1-cl]==ch) break; c=V[c].sufflink; } if(V[c].next.count(ch)) { s = V[c].next[ch]; return false; } s=++n; V[n].len=V[c].len+2; V[n].first=pos; V[c].next[ch]=n; if(V[n].len==1) { // even length V[n].sufflink=2; V[n].num=1; return true; } while(1) { c=V[c].sufflink; cl=V[c].len; if(pos-1-cl>=0 && S[pos-1-cl]==ch) { V[n].sufflink=V[c].next[ch]; break; } } V[n].num=1+V[V[n].sufflink].num; return true; } void init(string S) { this->S=S; V.clear(); V.resize(S.size()+10); n=s=2; V[1].first=V[2].first=-1; V[1].len=-1; V[2].len=0; V[1].sufflink=V[2].sufflink=1; } }; int L; string S; int pnode[505050]; int pre[505050],post[505050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; L=S.size(); PalindromicTree pt; pt.init(S); FOR(i,L) { pt.add(i); pnode[i]=pt.s; if(pt.V[pt.s].len==i+1) pre[i]=1; } x=pnode[L-1]; while(x>=3) { post[L-pt.V[x].len]=1; x=pt.V[x].sufflink; } for(i=L;i>=0;i--) post[i]+=post[i+1]; ll ret=0; for(i=2;i<=L-2;i++) { x=pnode[i-1]; while(x>=3) { if(pt.V[x].len