410634: GYM104067 I Интересные празднования

I. Интересные празднованияограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

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

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

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

• $$$\mathtt{seq}_1 = \text{«\t{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

Выходные данные

11

Входные данные

b

Выходные данные

0

Примечание

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