28544번 - Интересные празднования 다국어

Когда ваша семья празднует Хэллоуин каждый год, начинает хотеться как-то разнообразить празднование, чтобы Хэллоуин не надоедал.

Достоверно известно, что есть всего $26$ способов отпраздноват Хэллоуин, $i$-й из которых может быть обозначен $i$-й буквой латинского алфавита (от 'a' до 'z'). Семья Майерсов отмечает Хэллоуин уже очень давно, и, разумеется, они ведут записи о том, каким способом они его отмечали каждый год.

Теперь им стало интересно, сколько подпоследовательностей лет (не обязательно идущих подряд) были интересными. Всего есть ровно $26$ возможных интересных последовательностей способа отмечания, которые определяются следующим образом:

• $\mathtt{seq}_1 =$ <<a>>
• $\mathtt{seq}_{i+1} = \mathtt{seq}_i + \text{<<}c_{i+1}\text{>>} + \mathtt{seq}_i$, где $c_{i+1}$ --- $(i+1)$-й символ латинского алфавита.

Так, первые три интересные последовательности равны <<a>>, <<aba>> и <<abacaba>>.

Вам дана строка $s$, $i$-й символ которой равен способу отмечания Хэллоуина в $i$-й год. Помогите Майерсам определить количество ее подпоследовательностей, которые являются интересными. Поскольку это число может оказаться слишком большим, достаточно вычислить его по модулю $998244353$. Напомним, что подпоследовательностью называется строка, полученная из данной вычеркиванием некоторого, возможно нулевого, количества символов.

В единственной строке задана строка $s$ $(1 \leqslant |s| \leqslant 5000)$.

Выведите число подпоследовательностей этой строки вида $\mathtt{seq}_i$ по модулю $998244353$.

Из строки <<abacaba>> можно выбрать $4$ подпоследовательности <<a>>, $6$ подпоследовательностей <<aba>> и одну подпоследовательность <<abacaba>>.