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