P14553 [ROI 2013 Day1] 装配机器人

某高校的学生设计了一款机器人，用于部分自动化航空发动机的装配过程。 在发动机装配过程中可能遇到 26 种类型的操作，用小写拉丁字母表示。装配过程由 $N$ 个操作组成。计划使用机器人一次来执行装配过程中部分连续的操作。 机器人的内存由 $K$ 个单元组成，每个单元存储一个操作。操作按顺序执行，从第一个操作开始，按照它们在内存中的排列顺序进行。执行完最后一个操作后，机器人会从第一个操作继续工作。机器人可以在执行任意数量的操作后停止。如果机器人执行了至少 $(K + 1)$ 个操作，则机器人的使用在经济上是合理的。 需要编写一个程序，根据给定的装配过程确定机器人在经济上合理的使用方式数量。

输入文件的第一行写有数字 $K$（$1 \leqslant K < N$）——可以写入机器人内存的操作数量。 第二行由 $N$（$2 \leqslant N \leqslant 200,000$）个小写拉丁字母组成，表示操作——即发动机的装配过程。相同类型的操作用相同的字母表示。

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

### 说明 在第一个样例中，以下操作序列使用机器人在经济上是合理的： - 第 2 到第 4 个操作：`aba`，此时机器人内存中的操作为 `ab`； - 第 4 到第 6 个操作：`aca`，机器人内存中的操作为 `ac`； - 第 6 到第 8 个操作：`aba`，机器人内存中的操作为 `ab`； - 第 6 到第 9 个操作：`abab`，机器人内存中的操作为 `ab`； - 第 7 到第 9 个操作：`bab`，机器人内存中的操作为 `ba`。 ### 评分 本题包含三个子任务。每个子任务的评分使用独立的测试组。仅当通过相应组的所有测试时，子任务的得分才会被计入。 #### 子任务 1 $N \leqslant 100$。 该子任务分值为 30 分。 #### 子任务 2 $N \leqslant 5000$。 该子任务分值为 30 分。 #### 子任务 3 $N \leqslant 200,000$。 该子任务分值为 40 分。