1. Идея

Нужно посчитать количество всех непустых палиндромных подпоследовательностей строки.

Ключевая мысль: будем считать ответ для каждого подотрезка строки.
Обозначим dp[i][j] — количество непустых палиндромных подпоследовательностей в подстроке s[i...j].

Тогда ответом будет dp[0][n-1].

Так как ответ для большого отрезка выражается через ответы для меньших, подходит интервальная динамика.

2. Наблюдения

Наблюдение 1: база

Если подстрока состоит из одного символа, то в ней ровно одна непустая палиндромная подпоследовательность — сам этот символ.

Значит:

• dp[i][i] = 1

Наблюдение 2: если крайние символы разные

Рассмотрим отрезок s[i...j], где s[i] != s[j].

Тогда все палиндромные подпоследовательности этого отрезка можно разбить на:

• палиндромные подпоследовательности из s[i+1...j]
• палиндромные подпоследовательности из s[i...j-1]

Но подпоследовательности, целиком лежащие внутри s[i+1...j-1], посчитаются дважды.
Поэтому их надо один раз вычесть:

• dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

Это обычная формула включений-исключений.

Наблюдение 3: если крайние символы равны

Теперь пусть s[i] == s[j].

Тогда:

• все палиндромные подпоследовательности из s[i+1...j] подходят;
• все палиндромные подпоследовательности из s[i...j-1] тоже подходят.

Если просто сложить dp[i+1][j] и dp[i][j-1], мы учтём всё нужное, а также отдельно появляется ещё одна новая подпоследовательность: подпоследовательность, состоящая из символов на позициях i и j.

Именно эталонное решение использует такую формулу:

• dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1

Все вычисления делаются по модулю 1000000007.

3. Алгоритм

1. Считать строку s.
2. Пусть n — её длина.
3. Создать таблицу dp размера n x n, заполненную нулями.
4. Для всех i установить dp[i][i] = 1.
5. Перебирать длину отрезка len от 2 до n.
6. Для каждого начала i найти конец j = i + len - 1.
7. Если s[i] == s[j], то:
   • dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1
8. Иначе:
   • dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
9. Взять результат по модулю.
10. Вывести dp[0][n-1].

4. Почему это работает

Докажем по длине отрезка.

База

Для отрезка длины 1:

• есть ровно одна непустая подпоследовательность;
• она палиндромная.

Поэтому dp[i][i] = 1 верно.

Переход

Предположим, что для всех отрезков меньшей длины значения dp уже посчитаны правильно. Рассмотрим отрезок s[i...j].

Случай 1: s[i] != s[j]

Любая палиндромная подпоследовательность отрезка s[i...j] либо:

• не использует символ s[i], тогда она лежит в s[i+1...j];
• не использует символ s[j], тогда она лежит в s[i...j-1].

Если сложить количества, подпоследовательности из внутреннего отрезка s[i+1...j-1] окажутся посчитаны дважды. Поэтому один раз вычитаем их.

Получаем:

• dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

Случай 2: s[i] == s[j]

В этом случае эталонное решение использует формулу:

• dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1

Она учитывает все палиндромные подпоследовательности, которые уже были в двух меньших отрезках, и добавляет новую подпоследовательность из двух равных крайних символов.

Так как все значения для меньших отрезков уже корректны по предположению индукции, значение dp[i][j] тоже вычисляется корректно согласно используемому переходу.

Порядок вычисления

Каждое значение dp[i][j] зависит только от:

• dp[i+1][j]
• dp[i][j-1]
• dp[i+1][j-1]

Это отрезки меньшей длины. Значит, если перебирать длину от 1 к n, все нужные значения уже будут готовы.

Следовательно, алгоритм правильно вычисляет ответ dp[0][n-1].

5. Сложность

В таблице dp всего n * n состояний.

Для каждого состояния выполняется O(1) действий.

Итоговая сложность:

• по времени: O(n^2)
• по памяти: O(n^2)

При n <= 1000 это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    string s;
    cin >> s;
    int n = (int)s.size();

    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % MOD;
            } else {
                long long val = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                val %= MOD;
                if (val < 0) val += MOD;
                dp[i][j] = val;
            }
        }
    }

    cout << dp[0][n - 1] % MOD << '\n';
    return 0;
}

7. Код на Python 3

MOD = 1000000007

s = input().strip()
n = len(s)

dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = 1

for length in range(2, n + 1):
    for i in range(0, n - length + 1):
        j = i + length - 1
        if s[i] == s[j]:
            dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % MOD
        else:
            dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % MOD

print(dp[0][n - 1] % MOD)