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

문제

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

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

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

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

입력

В первой строке входного файла записано число $K$ ( $1 \leqslant K < N$ ) --- количество операций, которые можно записать в память робота.

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

출력

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

제한

$N \leqslant 200\\,000$

힌트

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

со 2-й по 4-ю: <<aba>>, при этом в памяти робота содержатся операции <<ab>>;
с 4-й по 6-ю: <<aca>>, в памяти робота <<ac>>;
с 6-й по 8-ю: <<aba>>, в памяти робота <<ab>>;
с 6-й по 9-ю: <<abab>>, в памяти робота <<ab>>;
с 7-й по 9-ю: <<bab>>, в памяти робота <<ba>>.