eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пошук паліндромів

Пошук паліндромів

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Рядок символів називається паліндромом, якщо він однаково читається в обох напрямках, наприклад, «madam», «bob».

Визначіть, скільки паліндромів заданої довжини K містить заданий рядок S.

Вхідні дані

У першому рядку міститься ціле число K (2K200), а у другому – заданий рядок S, який складається лише з латинських літер, причому великі і маленькі літери розрізняються (тобто «Bob» - не паліндром). Довжина S від 1 до 30000 символів.

Вихідні дані

У єдиному рядку повинна знаходитись кількість різних паліндромів довжини K, що містяться в S (тобто є послідовностями символів в S), що йдуть підряд (різними вважаються паліндроми, які починаються з різних позицій в S).

Приклад

Вхідні дані #1
3
babcbab
Вихідні дані #1
3