Правило 110

Аня прикрашає свій офіс стильними лампами. Вона використовує довгі світлодіодні стрічки, де кожна комірка вмикається або вимикається щосекунди за простим і елегантним алгоритмом. На кожному кроці стан кожної комірки ($0$ для вимкненої і $1$ для увімкненої) визначається на основі стану двох сусідніх комірок (лівої і правої) та власного стану, згідно з наступною таблицею:

Аня обирає початкову конфігурацію комірок і насолоджується анімацією, яка нагадує "Гру життя" Конвея, з цікавою поведінкою на межі між стабільністю і хаосом.

Вхідні дані

Перший рядок містить початкову конфігурацію у вигляді рядка з $16$ символів $0$ і $1$. Усі комірки зліва і справа від цього рядка вважаються $0$.

Другий рядок містить кількість $n(0\le n<2^{60})$ кроків, які потрібно виконати.

Світлодіодна стрічка вважається достатньо великою, щоб жодна $1$-комірка ніколи не досягла кінців стрічки.

Вихідні дані

Виведіть одне ціле число, яке представляє загальну кількість $1$-комірок у кінцевій конфігурації.

Приклади

Відповідь дорівнює $11$, виконані будуть наступні п'ять кроків:

...0000000010011011111000...
...0000000110111110001000...
...0000001111100010011000...
...0000011000100110111000...
...0000111001101111101000...
...0001101011111000111000...

де все, що не відображається, містить лише $0$-комірки.