题目描述

译自 ROI 2013 Day1 T2. Робот-сборщик

某大学的学生设计了一款机器人，用于部分自动化航空发动机装配过程。

在装配过程中，可能遇到 $26$ 种类型的操作，这些操作用小写拉丁字母表示。整个装配过程包含 $N$ 个操作。计划使用机器人一次性执行装配过程中一段连续的操作序列。

机器人的内存包含 $K$ 个单元，每个单元存储一个操作。机器人按内存中的顺序依次执行操作，从第一个开始，执行到最后一个后会循环回到第一个操作。可以在执行任意数量的操作后停止机器人。使用机器人被认为是经济上合理的前提是它至少执行了 $(K + 1)$ 个操作。

你需要编写一个程序，根据给定的装配过程，计算出使用机器人经济上合理的方式的数量。

输入格式

输入文件的第一行包含一个整数 $K$ $(1 \leq K < N)$，表示机器人内存中可以存储的操作数量。

第二行包含 $N$ $(2 \leq N \leq 200000)$ 个小写拉丁字母，表示发动机装配过程中的操作。同一类型的操作用相同的字母表示。

输出格式

输出文件应包含一个整数，表示使用机器人经济上合理的方式的数量。

2
zabacabab

5

在第一个样例中，使用机器人经济上合理的方式包括以下操作序列：

• 从第 $2$ 个到第 $4$ 个操作：aba，机器人内存中存储的操作是 ab；
• 从第 $4$ 个到第 $6$ 个操作：aca，机器人内存中存储的操作是 ac；
• 从第 $6$ 个到第 $8$ 个操作：aba，机器人内存中存储的操作是 ab；
• 从第 $6$ 个到第 $9$ 个操作：abab，机器人内存中存储的操作是 ab；
• 从第 $7$ 个到第 $9$ 个操作：bab，机器人内存中存储的操作是 ba。

2
abc

0

数据范围与提示

详细子任务附加限制及分值如下表所示：