Правило 110

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

Аня выбирает первоначальную конфигурацию ячеек и восхищается получившейся анимацией, которая очень похожа на "Игру жизни" Конвея, с интересным поведением на границе между стабильностью и хаосом.

Входные данные

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

Вторая строка содержит количество $n(0\le n<2^{60})$ шагов, которые необходимо выполнить.

Светодиодная лента считается достаточно большой, чтобы ни одна $1$-ячейка никогда не достигла концов ленты.

Выходные данные

Выведите одно целое число, которое представляет собой общее количество $1$-ячеек в окончательной конфигурации.

Примеры

Ответ равен $11$, выполнены будут следующие пять шагов:

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

где все, что не отображается, содержит только $0$-ячейки.