题目描述

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

在发动机装配过程中可能遇到 26 种类型的操作，用小写拉丁字母表示。装配过程由 $N$ 个操作组成。计划使用机器人一次来执行装配过程中部分连续的操作。

机器人的内存由 $K$ 个单元组成，每个单元存储一个操作。操作按顺序执行，从第一个操作开始，按照它们在内存中的排列顺序进行。执行完最后一个操作后，机器人会从第一个操作继续工作。机器人可以在执行任意数量的操作后停止。如果机器人执行了至少 $(K + 1)$ 个操作，则机器人的使用在经济上是合理的。

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

输入格式

输入文件的第一行写有数字 $K$（$1 \leqslant K < N$）——可以写入机器人内存的操作数量。

第二行由 $N$（$2 \leqslant N \leqslant 200,000$）个小写拉丁字母组成，表示操作——即发动机的装配过程。相同类型的操作用相同的字母表示。

输出格式

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

2
zabacabab

5

2
abc

0

提示

说明

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

• 第 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 分。