eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Робот-сборщик

Робот-сборщик

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

В процессе сборки двигателя могут встречаться операции 26 типов, которые обозначаются строчными буквами латинского алфавита. Процесс сборки состоит из n операций. Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.

Память робота состоит из k ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой операции. Робота можно остановить после выполнения любого количества операций. Использование робота экономически целесообразно, если он выполнит хотя бы (k + 1) операций.

Требуется написать программу, которая по заданному процессу сборки определяет количество экономически целесообразных способов использования робота.

Входные данные

В первой строке записано количество операций k (1k < n), которые можно записать в память робота.

Вторая строка состоит из n (2n200000) строчных латинских букв, обозначающих операции - процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.

Выходные данные

Вывести единственное целое число - количество экономически целесообразных способов использования робота.

Пояснение к примерам

В первом примере экономически целесообразно использовать робота для выполнения следующих последовательностей операций:

  • со 2-й по 4-ю: "aba", при этом в памяти робота содержатся операции "ab";

  • с 4-й по 6-ю: "aca", в памяти робота "ac";

  • с 6-й по 8-ю: "aba", в памяти робота "ab";

  • с 6-й по 9-ю: "abab", в памяти робота "ab";

  • с 7-й по 9-ю: "bab", в памяти робота "ba".

Пример

Входные данные #1
2
zabacabab
Выходные данные #1
5
Входные данные #2
2
abc
Выходные данные #2
0
Источник 2013 XXV Всероссийская олимпиада по информатике, 26 марта, Задача В