Робот-сборщик
Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.
В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из n операций. Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.
Память робота состоит из k ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой операции. Робота можно остановить после выполнения любого количества операций. Использование робота экономически целесообразно, если он выполнит хотя бы (k + 1) операций.
Требуется написать программу, которая по заданному процессу сборки определяет количество экономически целесообразных способов использования робота.
Входные данные
В первой строке записано количество операций k (1 ≤ k < n), которые можно записать в память робота.
Вторая строка состоит из n (2 ≤ n ≤ 200000) строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.
Выходные данные
Вывести единственное целое число - количество экономически целесообразных способов использования робота.
Пояснение к примерам
В первом примере экономически целесообразно использовать робота для выполнения следующих последовательностей операций:
со 2-й по 4-ю: "aba", при этом в памяти робота содержатся операции "ab";
с 4-й по 6-ю: "aca", в памяти робота "ac";
с 6-й по 8-ю: "aba", в памяти робота "ab";
с 6-й по 9-ю: "abab", в памяти робота "ab";
с 7-й по 9-ю: "bab", в памяти робота "ba".