#include using namespace std; #define rep(i,x,y) for(int i=(x);i<(y);++i) #define debug(x) #x << "=" << (x) #ifdef DEBUG #define _GLIBCXX_DEBUG #define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl #else #define print(x) #endif const int inf=1e9; const int64_t inf64=1e18; const double eps=1e-9; template ostream &operator<<(ostream &os, const vector &vec){ os << "["; for (const auto &v : vec) { os << v << ","; } os << "]"; return os; } using i64=int64_t; vector manacher(const string& s){ vector rad(s.size()); int i=0,j=0; while(i=0 and i+j=0 and i+k odd_palindrome(const string& s){ return manacher(s); } //res[i]:=s[i]とs[i+1]の間を中心とするような極大回分の半径.[i-rad[i]+1,i+rad[i]] vector even_palindrome(const string &s){ string t("$"); for(int i=0; i tmp=manacher(t),res(s.size()); for(int i=0; i> s; vector op=odd_palindrome(s),ep=even_palindrome(s); vector pp(s.size()); rep(i,0,s.size()){ { int l1=i-op[i]+1,r1=i+op[i]-1; if(l1==0){ rep(j,r1+1,s.size()){ { int l2=j-op[j]+1; if(l2<=r1+1) ++pp[j+j-r1-1]; } if(!ep[j]) continue; { int l2=j-ep[j]+1; if(l2<=r1+1) ++pp[j+j-r1]; } } } } if(!ep[i]) continue; { int l1=i-ep[i]+1,r1=i+ep[i]; if(l1==0){ rep(j,r1+1,s.size()){ { int l2=j-op[j]+1; if(l2<=r1+1) ++pp[j+j-r1-1]; } if(!ep[j]) continue; { int l2=j-ep[j]+1; if(l2<=r1+1) ++pp[j+j-r1]; } } } } } i64 ans=0; rep(i,0,s.size()){ rep(j,i+1,s.size()){ if(i+1