Robot Assembler

Time limit1sMemory limit1024 MB

Summary

Given a string of N operation types and a memory size K, count the ways to pick a K-character cyclic memory pattern and a starting position so that the robot runs at least K+1 operations before repeating the intended sequence.

Level: Hard8 of 10
Topics: String, Prefix sum, Combinatorics, String matching
Solved: No attempts yet

Problem

Students at a university designed a robot to partially automate the process of assembling an aircraft engine.

The engine assembly process can contain operations of 26 types, denoted by lowercase Latin letters. The assembly process consists of $N$ operations. The robot is intended to be used once to perform a part of consecutive operations from the assembly process.

The robot's memory consists of $K$ cells, each holding one operation. The operations are performed sequentially, starting from the first, in the order they are stored in memory. After performing the last of them, the robot continues from the first operation. The robot can be stopped after any number of operations have been performed. Using the robot is economically feasible if it performs at least $(K + 1)$ operations.

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

Input

The first line of the input file contains the number $K$ ( $1 \leqslant K < N$ ), the number of operations that can be written into the robot's memory.

The second line consists of $N$ ( $2 \leqslant N \leqslant 200\,000$ ) lowercase Latin letters denoting the operations, that is, the engine assembly process. Operations of the same type are denoted by the same letter.

Output

The output file must contain a single integer: the number of economically feasible ways to use the robot.

Constraints

$N \leqslant 200\,000$

Notes

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

from the 2nd to the 4th: <>, with the robot's memory holding the operations <>;
from the 4th to the 6th: <>, with the robot's memory holding <>;
from the 6th to the 8th: <>, with the robot's memory holding <>;
from the 6th to the 9th: <>, with the robot's memory holding <>;
from the 7th to the 9th: <>, with the robot's memory holding <>.

Examples2

Example 1
Input
```
2
zabacabab
```
Expected output
```
5
```
Example 2
Input
```
2
abc
```
Expected output
```
0
```