로봇 조립기

한 대학의 학생들이 항공기 엔진 조립 과정을 부분적으로 자동화할 로봇을 설계했다.

엔진 조립 과정에는 26가지 종류의 연산이 나타나며, 각각 라틴 소문자 하나로 표시된다. 조립 과정은 $N$개의 연산으로 이루어진다. 로봇은 조립 과정에서 연속한 일부 연산을 수행하는 데 한 번만 사용한다.

로봇의 메모리는 $K$개의 칸으로 이루어지고, 각 칸에는 연산 하나가 들어 있다. 연산은 메모리에 저장된 순서대로 첫 번째부터 차례로 수행된다. 마지막 연산을 수행한 뒤 로봇은 첫 번째 연산부터 작업을 이어 간다. 로봇은 몇 개의 연산을 수행한 뒤에도 멈출 수 있다. 로봇의 사용이 경제적으로 타당하다는 것은 로봇이 적어도 $(K + 1)$개의 연산을 수행하는 경우를 말한다.

조립 과정이 주어졌을 때 경제적으로 타당한 로봇 사용 방법의 수를 구하는 프로그램을 작성하라.

입력 파일의 첫째 줄에는 수 $K$ ($1 \leqslant K < N$)가 쓰여 있다. 이는 로봇의 메모리에 쓸 수 있는 연산의 개수이다.

둘째 줄은 $N$ ($2 \leqslant N \leqslant 200\,000$)개의 라틴 소문자로 이루어지며, 연산, 즉 엔진의 조립 과정을 나타낸다. 같은 종류의 연산은 같은 문자로 표시된다.

출력 파일에는 경제적으로 타당한 로봇 사용 방법의 수를 나타내는 정수 하나를 써야 한다.

• $N \leqslant 200\,000$

첫 번째 예에서 다음 연산열에 로봇을 사용하는 것이 경제적으로 타당하다.

• 2번째부터 4번째까지: <>, 로봇의 메모리에는 연산 <>가 들어 있다;
• 4번째부터 6번째까지: <>, 로봇의 메모리에는 <>;
• 6번째부터 8번째까지: <>, 로봇의 메모리에는 <>;
• 6번째부터 9번째까지: <>, 로봇의 메모리에는 <>;
• 7번째부터 9번째까지: <>, 로봇의 메모리에는 <>.