Задається рядок ~s~, який містить лише малі англійські літери. Даний рядок повторюється велику кількість разів і в результаті утворюється достатньо довгий рядок.

Завдання: знайти кількість входжень літери ~a~ в утворений довгий рядок до ~n~-го символа включно.

Наприклад, задається рядок ~s = abcac~ та ~n=10~. Перші десять символів утвореного рядка ~abcacabcac~ і кількість повторень літери ~a~ рівна 4.

Формат вхідних даних

Перший рядок вхідного потоку містить рядок ~s~ (~1 \le |s| \le 100~).

Другий рядок містить ціле число ~n~ (~1 \le n \le 10^{12}~).

Формат вихідних даних

Вивести шукану кількість входжень літери ~a~ до ~n~-го символа включно.

Приклад вхідних даних

abcac
10

Приклад вихідних даних

4

Приклад вхідних даних

aba
10

Приклад вихідних даних

7

Приклад вхідних даних

a
1000000000000

Приклад вихідних даних

1000000000000