#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 &rad,int l,int r){ l=l*2+1; r=r*2+1; int c=(l+r)/2; return r> s; vector pp(s.size()); vector rad=manacher(insert_dollar(s)); rep(i,0,s.size()){ rep(j,i+1,s.size()){ if(is_palindrome(rad,0,i) and is_palindrome(rad,i+1,j)) ++pp[j]; } } i64 ans=0; rep(i,0,s.size()) rep(j,i+2,s.size()) if(is_palindrome(rad,j,s.size()-1)) ans+=pp[i]; cout << ans << endl; } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(10); solve(); return 0; }