Problem
한 대학의 학생들은 항공기 엔진 조립 과정을 부분적으로 자동화하는 로봇을 설계했습니다.
엔진을 조립하는 과정에서 26가지의 동작이 일어날 수 있는데, 이는 라틴 알파벳의 소문자로 표시된다. 조립 프로세스는 N 작업으로 구성됩니다.
조립 과정에서 연속되는 작업의 일부를 로봇이 1회 사용하도록 되어 있습니다.
로봇의 메모리는 각각 하나의 작업을 포함하는 K 셀로 구성됩니다. 작업은 메모리에 있는 순서대로 첫 번째부터 시작하여 순차적으로 실행됩니다. 마지막 작업을 완료한 후 로봇은 첫 번째 작업을 계속합니다. 로봇은 작업 후 정지할 수 있습니다. 로봇을 사용하는 것은 적어도 K + 1 작업을 수행하는 경우 경제적으로 실행 가능합니다.
어셈블리 프로세스가 주어지면 로봇을 경제적으로 사용할 수 있는 방법의 수를 결정하는 프로그램을 작성해야 합니다.
입력
첫 번째 줄에는 로봇의 메모리에 기록할 수 있는 작업 수인 K > 0이 포함되어 있습니다.
두 번째 줄은 작업을 나타내는 N > K 소문자 라틴 문자로 구성됩니다. 엔진 조립 프로세스입니다. 동일한 유형의 작업은 동일한 문자(N <= 200000)로 표시됩니다.
출력
로봇을 사용하는 비용 효율적인 방법의 수인 단일 정수를 인쇄합니다.
<몸>
| 입력 |
출력 |
|
<사업부>2
자바카밥
|
5 |
2
ABC |
0 |