Рассмотрим следующую задачу.
Дана строка $$$s$$$, состоящая из $$$n$$$ строчных латинских букв, и целое число $$$k$$$ ($$$n$$$ не делится на $$$k$$$). Каждая буква — это одна из $$$c$$$ первых букв алфавита.
Вы применяете следующую операцию, пока длина строки больше $$$k$$$: выбрать непрерывную подстроку строки длины ровно $$$k$$$, удалить ее из строки и склеить полученные части вместе, не меняя порядка.
Пусть полученная строка длины строго меньше $$$k$$$ будет $$$t$$$. Какую лексикографически наименьшую строку $$$t$$$ можно получить?
Вам же дается обратная задача. По двум целым числам $$$n$$$ и $$$k$$$ ($$$n$$$ не делится на $$$k$$$) и строке $$$t$$$, состоящей из ($$$n \bmod k$$$) строчных латинских букв, посчитайте количество строк $$$s$$$, которые дают $$$t$$$, как лексикографически наименьшее решение.
Выведите это количество по модулю $$$998\,244\,353$$$.
В первой строке записаны три целых числа $$$n, k$$$ и $$$c$$$ ($$$1 \le n \le 10^6$$$; $$$2 \le k \le 10^6$$$; $$$1 \le c \le 26$$$; $$$n$$$ не делится на $$$k$$$) — длина строки $$$s$$$, длина удаляемой подстроки и количество первых букв алфавита.
Во второй строке записана $$$t$$$, состоящая из ровно ($$$n \bmod k$$$) строчных латинских букв. Каждая буква — это одна из $$$c$$$ первых букв алфавита.
Выведите одно целое число — количество строк $$$s$$$, которые дают $$$t$$$, как лексикографически наименьшее решение.
3 2 2 a
6
5 3 3 bc
15
34 12 26 codeforces
988024123
5 3 1 aa
1
Строки $$$s$$$ в первом примере: «aaa», «aab», «aba», «abb», «baa», «bba».
Строки $$$s$$$ во втором примере: «bcabc», «bcacc», «bcbbc», «bcbcc», «bccbc», «bcccc», «caabc», «cabbc», «cacbc», «cbabc», «cbbbc», «cbcbc», «ccabc», «ccbbc», «cccbc».
Название |
---|