1. Regexp

Задача Regexp

У вас є деякий текст S - послідовність маленьких літер латинського алфавіту. Вам необхідно знайти у цьому тексті кількість підрядків, які відповідають патерну, тобто шаблону.

Патерни у нас бувають лише вигляду “A*B” (замість A і B мають бути задані маленькі символи латиниці). Цей патерн означає наступне:

• рядок починається з символу A і закінчується символом B;
• довжина підрядка, що відповідає паттерну, не враховуючи А і В, ділиться націло на K.

Наприклад,  якщо маємо патерн e*s та k=2, то рядки “es”, “eggs”, “errors”, “ends” підходять під цей патерн, а ось рядки “elixirs”, “posix” або “regexp” - не підходять.

Технічні умови

Програма Regexp читає з стандартного пристрою введення (клавіатури) рядок S - заданий текст, що складається лише з малих символів латиниці, довжина якого не перевищує 100 000. З наступного рядка програма має зчитати патерн – рівно три символи, У останньому рядку міститься єдине натуральне число К, що не перевищує 100 000.

Програма виводить на стандартний пристрій виведення (екран) єдине число – шукану величину.

Приклади