Задана строка \(s\) длины \(n\), состоящая только из строчных букв латинского алфавита.
Подстрока строки — это последовательная подпоследовательность этой строки. Таким образом, строка «forces» является подстрокой «codeforces», а строка «coder» — нет.
Ваша задача — посчитать количество способов удалить ровно одну подстроку из этой строки таким образом, чтобы все оставшиеся символы были равны между собой (количество различных символов было равно единице или нулю).
Гарантируется, что в строке \(s\) существует хотя бы два различных символа.
Заметьте, что вы можете удалить всю строку и это является корректным способом. Также заметьте, что вам необходимо удалить хотя бы один символ.
Так как ответ может быть довольно большим (хотя не очень большим), выведите его по модулю \(998244353\).
Если вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.
Примечание
Пусть \(s[l; r]\) — подстрока строки \(s\) с позиции \(l\) по позицию \(r\) включительно.
Тогда в первом тестовом примере вы можете удалить следующие подстроки:
- \(s[1; 2]\);
- \(s[1; 3]\);
- \(s[1; 4]\);
- \(s[2; 2]\);
- \(s[2; 3]\);
- \(s[2; 4]\).
Во втором тестовом примере вы можете удалить следующие подстроки:
- \(s[1; 4]\);
- \(s[1; 5]\);
- \(s[1; 6]\);
- \(s[1; 7]\);
- \(s[2; 7]\);
- \(s[3; 7]\).
В третьем тестовом примере вы можете удалить следующие подстроки:
- \(s[1; 1]\);
- \(s[1; 2]\);
- \(s[2; 2]\).