Problem
Studenten einer Universität haben einen Roboter entworfen, um die Montage eines Flugzeugmotors teilweise zu automatisieren.
Bei der Montage des Motors können 26 Arten von Operationen vorkommen, die mit Kleinbuchstaben des lateinischen Alphabets gekennzeichnet sind. Der Erstellungsprozess besteht aus N Operationen.
Es wird davon ausgegangen, dass der Roboter einmal verwendet wird, um einen Teil der aufeinanderfolgenden Operationen aus dem Montageprozess durchzuführen.
Der Speicher des Roboters besteht aus K-Zellen, von denen jede eine Operation enthält. Die Vorgänge werden nacheinander ab der ersten in der Reihenfolge ausgeführt, in der sie sich im Speicher befinden. Nachdem Sie den letzten abgeschlossen haben, setzt der Roboter die Arbeit mit dem ersten fort. Der Roboter kann nach jeder Operation gestoppt werden. Der Einsatz eines Roboters ist wirtschaftlich sinnvoll, wenn er mindestens K + 1-Operationen ausführt.
Sie müssen ein Programm schreiben, das anhand eines bestimmten Montageprozesses die Anzahl der wirtschaftlich angemessenen Methoden zur Verwendung des Roboters bestimmt.
Eingabe
Die erste Zeile enthält die Anzahl K > 0 - die Anzahl der Operationen, die in den Speicher des Roboters geschrieben werden können.
Die zweite Zeile besteht aus N > K lateinischen Kleinbuchstaben, die Operationen bezeichnen - der Prozess der Motormontage. Operationen desselben Typs werden mit demselben Buchstaben gekennzeichnet (N <= 200000).
Ausgabe
Geben Sie eine einzige Ganzzahl aus - die Anzahl der wirtschaftlich angemessenen Möglichkeiten, den Roboter zu benutzen.
| Eingabe |
Ausgabe |
|
2
zabacabab
|
5 |
2
abc |
0 |