#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a hash,p; RollingHash(){} RollingHash(const string &s,ull B=1000000007LL){ int n=s.size(); hash.assign(n+1,0); p.assign(n+1,1); for(int i=0;i>s; int n=s.size(); string t=s; reverse(t.begin(),t.end()); RollingHash rs(s),rt(t); auto check=[&](int l,int r){ return rs.find(l,r)==rt.find(n-r,n-l); }; vector dp(n+1,0); for(int r=1;r<=n;r++) for(int m=1;m