/* -*- coding: utf-8 -*- * * 464.cc: No.464 PPAP - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 5000; typedef long long ll; const int INF = 1 << 30; const ll LINF = 1LL << 60; /* typedef */ typedef vector vi; typedef queue qi; typedef pair pii; /* global variables */ bool pls[MAX_N][MAX_N + 1]; vi nbrs[MAX_N]; int ssums[MAX_N + 1], gsums[MAX_N + 1]; /* subroutines */ /* main */ int main() { string s; cin >> s; int n = s.size(); for (int i = 0; i < n; i++) { pls[i][i] = pls[i][i + 1] = true; nbrs[i].push_back(i + 1); } for (int l = 2; l <= n; l++) for (int i = 0, j = l; j <= n; i++, j++) if (s[i] == s[j - 1] && pls[i + 1][j - 1]) { pls[i][j] = true, nbrs[i].push_back(j); //printf("%d,%d\n", i, j); } for (int i = n - 1; i >= 0; i--) gsums[i] = gsums[i + 1] + (pls[i][n] ? 1 : 0); vi &nbr0 = nbrs[0]; for (vi::iterator vit0 = nbr0.begin(); vit0 != nbr0.end(); vit0++) { vi &nbr1 = nbrs[*vit0]; for (vi::iterator vit1 = nbr1.begin(); vit1 != nbr1.end(); vit1++) ssums[*vit1]++; } int sum = 0; for (int i = 0; i < n; i++) sum += ssums[i] * gsums[i + 1]; printf("%d\n", sum); return 0; }