Задається рядок \(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