J. Сколько разбиений на палиндромы

Посчитайте количество способов разрезать строку на палиндромы по модулю $10^9 + 7$. Разбиения различаются набором позиций разрезов.

Схема та же, что в классной задаче про наименьшее число кусков, но вместо минимума - сумма:

Это общее правило: одна и та же динамика с $\min$ считает оптимум, с суммой - количество. Меняется только операция сборки, а состояния и переходы те же.

Ответ всегда не меньше единицы: разбиение на отдельные буквы существует всегда.

При $n = 5000$ ответ огромен - отсюда и модуль. Не забудьте брать остаток на каждом шаге, а не в конце.

Одна строка длины $n$ ($1 \le n \le 5000$) из строчных латинских букв.

Одно число - количество разбиений по модулю $10^9 + 7$.