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

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

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

Input

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

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

Output

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

Sample Input 1

abcac
10

Sample Output 1

4

Sample Input 2

aba
10

Sample Output 2

7

Sample Input 3

a
1000000000000

Sample Output 3

1000000000000