481b.cpp

#include <iostream>
#include <vector>

int main() {
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);

//  Считываем строчку
    std::string str;
    std::cin >> str;

    int n = (int) str.length();

//  Исходная матрица количества палиндромов count:
    std::vector<std::vector<int>> count(n, std::vector<int>(n));

//  Заполнение ее единичками/ноликами в зависимости от совпадений символов на концах (сразу переворачиваем матрицу для удобства)
    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
            count[n-i-1][j] = (str[i] == str[j]);

//  Матрица интегральных сумм:
    std::vector<std::vector<int>> sum(1+n, std::vector<int>(1+n));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            //  Пересчет текущего количества:
            if (count[i][j]) {
                count[i][j] += sum[i][j];
            }
            //  Пересчет интегральной суммы:
            sum[i+1][j+1] = sum[i][j+1]+sum[i+1][j]-sum[i][j]+count[i][j];
        }

//  Вывод ответа:
    std::cout << sum[n][n];

    return 0;
}