#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c manacher(const string &s){ int n = s.size(), c = 0; vector rad(n); for(int r=0;r= 0 && rr < n && s[rl] == s[rr]) rr++, rl--; rad[r] = rr - r; c = r; } } return rad; } string insert_dollar(const string &s){ int n = s.size(); string ret(n*2+1, '$'); for(int i=0;i &rad){ l = l * 2 + 1; r = (r - 1 ) * 2 + 1; int c = (l + r ) / 2; return r < c + rad[c]; } int main(int argc, char const *argv[]) { string s;std::cin >> s; vector v = manacher(insert_dollar(s)); ll ans = 0; for(ll i=0;i