#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#include //#include //#include //#include //#include //#include //#include //#include //#if __cplusplus >= 201103L //#include //#include //#include //#include // //#define cauto const auto& //#else //#endif using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef vector vint; typedef vector > vvint; typedef vector vll, vLL; typedef vector > vvll, vvLL; #define VV(T) vector > template void initvv(vector > &v, int a, int b, const T &t = T()){ v.assign(a, vector(b, t)); } template void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define reep(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) reep((i),0,(n)) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define F first #define S second #define mkp make_pair #define RALL(v) (v).rbegin(),(v).rend() #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define MOD 1000000007LL #define EPS 1e-8 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define maxs(x,y) x=max(x,y) #define mins(x,y) x=min(x,y) template struct RollingHash { static const int NN = 1; // the number of hash table T base[2] = {1009, 1007}; T PMOD[2] = {1000000007, 1000000009}; vector hash[2]; vector mypow[2]; int sz; void init(string s) { sz = s.size(); for(int i = 0; i < NN; i++) { hash[i].assign(sz + 1, 0); mypow[i].assign(sz + 1, 0); mypow[i][0] = 1; } for(int i = 0; i < NN; i++) { for(int j = 0; j < sz; j++) { hash[i][j + 1] = (hash[i][j] * base[i] + s[j]) % PMOD[i]; mypow[i][j + 1] = mypow[i][j] * base[i] % PMOD[i]; } } } RollingHash() { } // hash[t] value of s[l..r] T get(int l, int r, int t) { T ret = (hash[t][r + 1] - hash[t][l] * mypow[t][r - l + 1] % PMOD[t] + PMOD[t]) % PMOD[t]; return ret; } // compare s[a..b] and s[c..d] O(1) bool comp(int a, int b, int c, int d) { if(a < 0 || sz <= b || c < 0 || sz <= d) return false; for(int i = 0; i < NN; i++) { if(get(a, b, i) != get(c, d, i)) return false; } return true; } // longest common extension s[l..LCE(l,r)] == s[r..LCE(l,r)] && s[l..LCE(l,r)+1] != s[r..LCE(l,r)+1] int LCE(int l,int r){ tie(l,r)=minmax(l,r); if(l==r) return sz-r+1; int ll = 0; int rr = sz; while(rr-ll>1){ int mid = (ll+rr)>>1; if(comp(l,l+mid-1,r,r+mid-1)) ll=mid; else rr=mid; } return ll; } }; RollingHash rh; string s; int n; int LCE(int l, int r){ return rh.LCE(l, r); } static const int MAX_SIZE = 1 << 14; //segment tree のサイズ。 2^17 ≒ 1.3 * 10^5 ll all[2 * MAX_SIZE - 1], part[2 * MAX_SIZE - 1]; // segment tree //区間[a, b)に値xを加算する. void add(int a, int b, ll x, int k = 0, int l = 0, int r = MAX_SIZE) { if (a <= l && r <= b){ //[l, r)が[a, b)に完全に内包されていれば all[k] += x; //[l, r)の全ての区間が持つ値としてxを足す. } else if (l < b && a < r){ //[l, r)と[a, b)が交差していれば part[k] += (min(b, r) - max(a, l)) * x; //交差している分の値を, 部分的な和を持つノードに加算する. add(a, b, x, k * 2 + 1, l, (l + r) / 2); //子でも同じ処理を行う. add(a, b, x, k * 2 + 2, (l + r) / 2, r); //〃. } } ll sum(int a, int b, int k = 0, int l = 0, int r = MAX_SIZE) { if (b <= l || r <= a){ //[a, b)と[l, r)が全く交差しない場合 return (0); } else if (a <= l && r <= b){ //完全に内包されていれば return (all[k] * (r - l) + part[k]); } else { //[l, r)と[a, b)が交差していれば ll res; res = (min(b, r) - max(a, l)) * all[k]; //そのノードの全ての要素が持つ値のうち, [a, b)に属すものの分だけを加算する. res += sum(a, b, k * 2 + 1, l, (l + r) / 2); //子ノードで和を求める. res += sum(a, b, k * 2 + 2, (l + r) / 2, r); //〃 return (res); } } bool isPal(string a){ string b = a; reverse(ALL(b)); return a == b; } int func(string a){ int ret = 0; rep(i,a.size()-1){ if(isPal(a.substr(0,i+1))&&isPal(a.substr(i+1))) { ret++; } } return ret; } // int ff(string a){ // int n = a.size(); // rep(i,n){ // rep(j,i){ // for(int k=i+2) // } // } // } set> se; void mainmain(){ cin>>s; n = s.size(); string r = s; reverse(ALL(r)); rh.init(s+'$'+r); vll a(n); rep(i,n-1){ int le = i+1; if(le&1){ int tl = le/2; int c = i-tl; if(tl == LCE(c+1, 2*n-(c-1))) a[i+1]=1; } else{ int tl = le/2; int c = i-tl; if(tl == LCE(c+1, 2*n-c)) a[i+1]=1; } } // rep(i,n){ // cout<F.F,rr=it->F.S,t=it->S; // if(i==5) cout<F.F,rr=it->F.S,t=it->S; // if(i==1) cout<=0;i--){ c[i] += c[i+1]; } ll ans = 0; rep(i,n-2){ ans += b[i] * c[i+2]; } cout << ans << endl; // cout<