Когда ваша семья празднует Хэллоуин каждый год, начинает хотеться как-то разнообразить празднование, чтобы Хэллоуин не надоедал.
Достоверно известно, что есть всего $$$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».