Problem
Gli studenti di una delle università hanno progettato un robot per automatizzare parzialmente il processo di assemblaggio di un motore aeronautico.
Nel processo di assemblaggio del motore possono verificarsi 26 tipi di operazioni, indicate da lettere minuscole dell'alfabeto latino. Il processo di assemblaggio consiste in N operazioni.
Dovrebbe utilizzare il robot una volta per eseguire parte delle operazioni consecutive dal processo di assemblaggio.
La memoria del robot è composta da K celle, ciascuna contenente un'operazione. Le operazioni vengono eseguite in sequenza, a partire dalla prima, nell'ordine in cui si trovano in memoria. Dopo aver completato l'ultimo, il robot continua con il primo. Il robot può essere arrestato dopo qualsiasi operazione. L'utilizzo di un robot è economicamente conveniente se esegue almeno K + 1 operazioni.
Devi scrivere un programma che, dato il processo di assemblaggio, determinerà il numero di modi economicamente fattibili per utilizzare il robot.
Input
La prima riga contiene il numero K > 0 - il numero di operazioni che possono essere scritte nella memoria del robot.
La seconda riga è composta da N > K lettere latine minuscole che denotano operazioni - processo di assemblaggio del motore. Le operazioni dello stesso tipo sono denotate dalla stessa lettera (N <= 200000).
Uscita
Stampa un singolo numero intero: il numero di modi convenienti per utilizzare il robot.
| Input |
Uscita |
|
2
zabacabab
|
5 |
2
abc |
0 |