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

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

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

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

Так, первые три интересные последовательности равны «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».