시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из $N$ операций. Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
Память робота состоит из $K$ ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой операции. Робота можно остановить после выполнения любого количества операций. Использование робота экономически целесообразно, если он выполнит хотя бы $(K + 1)$ операций.
Требуется написать программу, которая по заданному процессу сборки определяет количество экономически целесообразных способов использования робота.
В первой строке входного файла записано число $K$ ($1 \leqslant K < N$) --- количество операций, которые можно записать в память робота.
Вторая строка состоит из $N$ ($2 \leqslant N \leqslant 200\,000$) строчных латинских букв, обозначающих операции --- процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.
Выходной файл должен содержать единственное целое число --- количество экономически целесообразных способов использования робота.
2 zabacabab
5
2 abc
0
В первом примере экономически целесообразно использовать робота для выполнения следующих последовательностей операций: