#include using namespace std; class Manacher { private: const string &s; vector rad; public: Manacher(const string &s) : s(s), rad(s.size() * 2 - 1) { const int n = rad.size(); int i = 0; int j = 0; while (i < n) { while (i - j >= 0 && i + j < n && get(i - j) == get(i + j)) { j++; } rad[i] = j; int k = 1; while (i - k >= 0 && i + k < n && k + rad[i - k] < j) { rad[i + k] = rad[i - k]; k++; } i += k; j -= k; } } // [l,r) bool isPalindrome(int l, int r) { return rad[l + r - 1] >= r - l; } private: char get(int k) { return k % 2 == 0 ? s[k / 2] : '$'; } }; int main() { string s; cin >> s; int n = s.size(); Manacher mana(s); vector P(n + 1); for (int i = 1; i < n; i++) { if (mana.isPalindrome(0, i)) { P[i]++; } } vector PP(n + 1); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (mana.isPalindrome(i, j)) { PP[j + 1] += P[i]; } } } for (int i = 0; i < n; i++) { PP[i + 1] += PP[i]; } int64_t PPAP = 0; for (int i = 0; i < n; i++) { if (mana.isPalindrome(i, n)) { PPAP += PP[i]; } } cout << PPAP << endl; }