Problem
Alunos de uma das universidades projetaram um robô para automatizar parcialmente o processo de montagem de um motor de aeronave.
No processo de montagem do motor podem ocorrer 26 tipos de operações, que são indicadas por letras minúsculas do alfabeto latino. O processo de montagem consiste em N operações.
É suposto usar o robô uma vez para realizar parte das operações consecutivas do processo de montagem.
A memória do robô consiste em K células, cada uma contendo uma operação. As operações são executadas sequencialmente, começando pela primeira, na ordem em que estão localizadas na memória. Depois de completar o último, o robô continua com o primeiro. O robô pode ser parado após qualquer operação. O uso de um robô é economicamente viável se ele realizar pelo menos K + 1 operações.
Você precisa escrever um programa que, dado o processo de montagem, determine o número de formas economicamente viáveis de usar o robô.
Entrada
A primeira linha contém o número K > 0 - o número de operações que podem ser gravadas na memória do robô.
A segunda linha consiste em N > K letras latinas minúsculas denotando operações - processo de montagem do motor. Operações do mesmo tipo são indicadas pela mesma letra (N <= 200000).
Saída
Imprima um único inteiro - o número de maneiras econômicas de usar o robô.
Entrada |
Saída |
2
zabacabab
|
5 |
2
abc |
0 |