Students from one of the universities designed a robot to partially automate the process of assembling an aircraft engine.
In the process of assembling the engine, 26 types of operations can occur, which are indicated by lowercase letters of the Latin alphabet. The assembly process consists of N operations.
It is supposed to use the robot once to perform part of the consecutive operations from the assembly process.
The robot's memory consists of K cells, each containing one operation. Operations are executed sequentially, starting with the first, in the order in which they are located in memory. After completing the last one, the robot continues with the first one. The robot can be stopped after any operation. Using a robot is economically viable if it performs at least K + 1 operations.
You need to write a program that, given the assembly process, will determine the number of economically viable ways to use the robot.
Input
The first line contains the number K > 0 - the number of operations that can be written to the robot's memory.
The second line consists of N > K lowercase Latin letters denoting operations - engine assembly process. Operations of the same type are denoted by the same letter (N <= 200000).
Output
Print a single integer - the number of cost-effective ways to use the robot.
| Input |
Output |
|
2
zabacabab
|
5 |
2
abc |
0 |