| Чемпионат КРОК 2016 - Отборочный Раунд |
|---|
| Закончено |
После того как Бесси уволили из газеты за незнание алфавита, она решила пойти учиться и устроилась в Академию Филе Миньон. У неё уже наблюдается определённый прогресс: она выучила первые k букв английского алфавита.
Каждое утро Бесси идёт на учёбу вдоль дорожки, состоящей из m + n плиток. Чтобы помочь Бесси не растерять знания, профессор Муузинг нарисовал на каждой из первых m плиток одну из k первых строчных букв английского алфавита, получив строку t. Муузинг восхищён тем, какая Бесси способная ученица, поэтому разрешил ей самостоятельно заполнить буквами оставшиеся n плиток.
Пусть в итоге получится строка s (|s| = m + n), состоящая из букв, написанных на плитках в порядке от дома к академии. Для любой последовательности индексов p1 < p2 < ... < pq можно определить соответствующую подпоследовательность строки s как строку sp1sp2... spq. Две подпоследовательности считаются различными, если различаются соответствующие им строки. Бесси хочет расставить буквы на оставшихся плитках таким образом, чтобы количество различных подпоследовательностей было как можно больше. Поскольку Бесси ещё продолжает учить алфавит, ей явно потребуется ваша помощь!
Обратите внимание, что пустая подпоследовательность тоже учитывается в ответе.
В первой строке входных данных записаны два числа n и k (0 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 26).
Во второй строке находится строка t (|t| = m, 1 ≤ m ≤ 1 000 000), состоящая из первых k строчных букв английского алфавита.
Определите максимальное количество различных подпоследовательностей, которое может быть у итоговой строки, после того как Бесси заполнит оставшиеся плитки первыми k буквами английского алфавита. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.
Обратите внимание, что вас не просят максимизировать остаток от деления на 109 + 7! Требуется максимизировать изначальное значение, а потом вывести остаток.
1 3
ac
8
0 2
aaba
10
В первом примере оптимальный способ пометить буквами оставшиеся плитки даёт 8 различных подпоследовательностей: «» (пустая строка), «a», «c», «b», «ac», «ab», «cb» и «acb».
Во втором примере все плитки уже размечены буквами. Существует 10 различных подпоследовательностей: «» (пустая строка), «a», «b», «aa», «ab», «ba», «aaa», «aab», «aba» и «aaba». Обратите внимание, что некоторые строки, например «aa», могут быть прочитаны разными способами, но учитываются только один раз.
