#include using lint=long long; void debug_impl(){std::cerr<<'\n';} templatevoid debug_impl(Head head, Tail... tail){std::cerr << " " << head;debug_impl(tail...);} template::value,std::nullptr_t> = nullptr> std::ostream&operator<<(std::ostream&os,Container const&v) {os<<"{";for(auto it=v.begin();it!=v.end();it++){os<<(it!=v.begin()?",":"")<<*it;}return os<<"}";} templateclass Tuple,class...Args,std::size_t...Inds,std::size_t=std::tuple_size>::value> std::ostream&tuple_output_impl(std::ostream&os,const Tuple&tuple,std::integer_sequence) {os<<"(";(void)std::initializer_list{((void)(os<<(Inds>0?",":"")<(tuple)),0)...};return os<<")";} templateclass Tuple,class...Args,std::size_t=std::tuple_size>::value> std::ostream&operator<<(std::ostream&os,const Tuple&tuple) {return tuple_output_impl(os,tuple,std::index_sequence_for());} #define DEBUG 1 #if DEBUG #define debug(...)do{std::cerr<>s; lint n=s.length(); lint ans=0; for(lint sum=1;sum<2*n;sum++){ for(lint l=(sum+1)/2-1,r=sum/2+1;0<=l&&r<=n;l--,r++){ if(s.at(l)!=s.at(r-1))break; if(r-l