I. Обратная задача
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим следующую задачу.

Дана строка $$$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».