import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int[] manacher(T)(T a) { const n = cast(int)(a.length); int[] r = new int[n * 2]; for (int i = 0, j = 0, k; i < n * 2; i += k, j = max(j - k, 0)) { for (; 0 <= i - j && i + j + 1 < n * 2 && a[(i - j) / 2] == a[(i + j + 1) / 2]; ++j) {} r[i] = j; for (k = 1; 0 <= i - k && 0 <= j - k && r[i - k] != j - k; ++k) { r[i + k] = min(r[i - k], j - k); } } return r; } class Eertree(int shift, char offset) { string s; int n; int[] us, len, fail; int[] next; this(in string s) { this.s = s; n = cast(int)(s.length); us = new int[n + 3]; len = new int[n + 3]; fail = new int[n + 3]; next = new int[(n + 3) << shift]; us[1] = 1; len[1] = -1; fail[1] = 1; us[2] = 2; len[2] = 0; fail[2] = 1; foreach (i; 0 .. n) { const c = s[i] - offset; int u = us[i + 2]; for (; !isSuffix(i, u); u = fail[u]) {} if (!next[u << shift | c]) { next[u << shift | c] = i + 3; len[i + 3] = len[u] + 2; if (u == 1) { fail[i + 3] = 2; } else { int v = fail[u]; for (; !isSuffix(i, v); v = fail[v]) {} fail[i + 3] = next[v << shift | c]; } } us[i + 3] = next[u << shift | c]; } } bool isSuffix(int i, int u) const { const j = i - 1 - len[u]; return (j >= 0 && s[j] == s[i]); } void print() const { void dfs(int u, string prefix, int type) { writefln("%s%s%s %s %s", prefix, ["", "|-- ", "`-- "][type], (len[u] <= 0) ? ("(" ~ len[u].to!string ~ ")") : s[u - 2 - len[u] .. u - 2], u, fail[u]); const vs = next[u << shift .. (u + 1) << shift].filter!(v => v).array; foreach (v; vs) { dfs(v, prefix ~ ["", "| ", " "][type], (v == vs[$ - 1]) ? 2 : 1); } } dfs(1, "", 0); dfs(2, " ", 0); } } enum LIM_LOG_N = 19; int N; string S; void main() { try { for (; ; ) { S = readToken(); N = cast(int)(S.length); const rads = manacher(S); const tree = new Eertree!(5, 'a')(S); debug { writeln("S = ", S); writeln("rads = ", rads); tree.print; } // [a, b) bool isPal(int a, int b) { assert(0 <= a && a < b && b <= N); return (b - a <= rads[a + b - 1]); } int[] palsL; foreach (i; 1 .. N + 1) { if (isPal(0, i)) { palsL ~= i; } } auto cntR = new int[N + 1]; foreach_reverse (i; 0 .. N) { cntR[i] = (isPal(i, N) ? 1 : 0) + cntR[i + 1]; } debug { writeln("palsL = ", palsL); writeln("cntR = ", cntR); } auto depth = new int[N + 3]; foreach (u; 3 .. N + 3) { if (tree.us[u] == u) { depth[u] = depth[tree.fail[u]] + 1; } } auto f = new int[][](LIM_LOG_N, N + 3); foreach (u; 1 .. N + 3) { f[0][u] = tree.fail[u]; } foreach (e; 1 .. LIM_LOG_N) { foreach (u; 1 .. N + 3) { f[e][u] = f[e - 1][f[e - 1][u]]; } } long ans; foreach (i; 1 .. N) { const r = palsL.lowerBound(i); int u = tree.us[i + 2]; if (tree.len[u] == i) { u = tree.fail[u]; } // left greedy if (r > 0 && isPal(palsL[r - 1], i)) { int sum = 0; if (tree.len[u] > i - palsL[r - 1] && isPal(0, i - tree.len[u])) { int v = u; foreach_reverse (e; 0 .. LIM_LOG_N) { const w = f[e][v]; if (tree.len[w] > i - palsL[r - 1] && isPal(0, i - tree.len[w])) { sum |= 1 << e; v = w; } } ++sum; } debug { writeln("left ", S[0 .. palsL[r - 1]], "|", S[palsL[r - 1] .. i]); writeln(" ", sum); int cnt; foreach (j; 1 .. i) { if (isPal(0, j) && isPal(j, i)) { ++cnt; } } assert(cnt == 1 + sum); } ans += 1L * (1 + sum) * cntR[i + 1]; continue; } // right greedy if (u > 2 && isPal(0, i - tree.len[u])) { const l = palsL.upperBound(i - tree.len[u]); int lo = l - 1, hi = r; for (; lo + 1 < hi; ) { const mid = (lo + hi) / 2; isPal(palsL[mid], i) ? (hi = mid) : (lo = mid); } debug { writeln("right ", S[0 .. i - tree.len[u]], "|", S[i - tree.len[u] .. i]); writeln(" [", l, ", ", r, ") ", hi); int cnt; foreach (j; 1 .. i) { if (isPal(0, j) && isPal(j, i)) { ++cnt; } } assert(cnt == 1 + (r - hi)); } ans += 1L * (1 + (r - hi)) * cntR[i + 1]; continue; } } writeln(ans); } } catch (EOFException e) { } }