Робот-збирач
Студенти одного з університетів розробили робота для часткової автоматизації процесу складання авіаційного двигуна.
Під час складання двигуна можуть виконуватися операції 26 типів, які позначаються малими літерами латинського алфавіту. Процес складання складається з n операцій. Робота планується використовувати один раз для виконання частини послідовних операцій з цього процесу.
Пам'ять робота складається з k комірок, кожна з яких може містити одну операцію. Операції виконуються послідовно, починаючи з першої, у тому порядку, в якому вони розташовані в пам'яті. Після виконання останньої операції робот повертається до першої. Робота можна зупинити після виконання будь-якої кількості операцій. Використання робота є економічно доцільним, якщо він виконає принаймні (k + 1) операцій.
Необхідно написати програму, яка за заданим процесом складання визначить кількість економічно доцільних способів використання робота.
Вхідні дані
У першому рядку записано кількість операцій k (1 ≤ k < n), які можуть бути записані в пам'ять робота.
Другий рядок містить n (2 ≤ n ≤ 200000) малих латинських літер, що позначають операції - процес складання двигуна. Операції одного типу позначаються однією і тією ж літерою.
Вихідні дані
Виведіть єдине ціле число - кількість економічно доцільних способів використання робота.
Пояснення до прикладів
У першому прикладі економічно доцільно використовувати робота для виконання наступних послідовностей операцій:
з 2-ї по 4-ту: "aba", при цьому в пам'яті робота містяться операції "ab";
з 4-ї по 6-ту: "aca", в пам'яті робота "ac";
з 6-ї по 8-му: "aba", в пам'яті робота "ab";
з 6-ї по 9-ту: "abab", в пам'яті робота "ab";
з 7-ї по 9-ту: "bab", в пам'яті робота "ba".