시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB1000.000%

문제

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

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

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

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

입력

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

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

출력

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

제한

  • $N \leqslant 200\,000$

예제 입력 1

2
zabacabab

예제 출력 1

5

예제 입력 2

2
abc

예제 출력 2

0

힌트

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

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