#include #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef unsigned long long ll; ll B=1e9+7; int S[1000000]; ll hs[1000001]; map has; //has->num map D,E; map nxt; map > prv; set doll; //$..$ void Manacher(string s){ int i=0,j=0; while(i=0&&i+j=0&&i+k>s_; int N=s_.size(); s=s_[0]; rep1(i,N-1) s+="$",s+=s_[i]; N=s.size(); Manacher(s); rep(i,N) hs[i+1]=hs[i]*B+s[i]; rep(i,N){ int x=S[i]; ll h=H(i-x+1,i+x); bool fst=1; while(!has.count(h)){ if(fst) has[h]++,fst=0; has[h]; //access if(s[i-x+1]=='$') doll.insert(h); x--; if(x==0) break; ll nh=H(i-x+1,i+x); nxt[h]=nh; prv[nh].pb(h); h=nh; } if(fst) has[h]++; } for(auto p:has){ ll h=p.fs; if(!nxt.count(h)) dfs(h); } } int main(){ solve(); D=has; rep(i,1000000) S[i]=0; rep(i,1000001) hs[i]=0; has.clear(); nxt.clear(); prv.clear(); solve(); E=has; ll ans=0; /* for(auto p:E){ ll h=p.fs; show(h); show(E[h]); }*/ for(auto p:D){ ll h=p.fs; if(doll.count(h)) continue; if(E.count(h)){ ans+=D[h]*E[h]; } } cout<