Students of one university designed a robot to partially automate the assembly process of an aircraft engine.

During the process of engine assembly, operations of 26 types may occur, which are denoted 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 successive operations from the assembly process.

The robot's memory consists of k cells, each contains one operation. Operations are performed sequentially, starting with the first, in the order in which they are located in the memory. Having completed the last of them, the robot continues to work from the first operation. The robot can be stopped after performing any number of operations. Using a robot is economically feasible if it performs at least (k + 1) operations.

Write a program that, according to a given assembly process, determines the number of economically expedient ways to use the robot.

Input

First line contains the number of operations k (1 ≤ k < n) that can be recorded in the robot's memory.

Second line consists of n (2 ≤ n ≤ 200000) lowercase Latin letters, denoting the operations - the process of assembling an engine. Operations of the same type are denoted with the same letter.

Output

Print one integer - the number of economically expedient ways to use the robot.

Explanations to sample cases

In the first example, it is economically feasible to use a robot to perform the following sequences of operations:

• from 2-nd tо 4-th: "aba", robot's memory contains operations "ab";
• from 4-th to 6-th: "aca", robot's memory contains operations "ac";
• from 6-th to 8-th: "aba", robot's memory contains operations "ab";
• from 6-th to 9-th: "abab", robot's memory contains operations "ab";
• from 7-th to 9-th: "bab", robot's memory contains operations "ba".