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>>.