Аня украшает свой офис самыми крутыми лампами. Она использует очень длинные светодиодные ленты, в которых каждая отдельная ячейка включается или выключается каждую секунду по следующему простому и красивому алгоритму. На каждом шаге статус каждой ячейки ($0$ для выкл. и $1$ для вкл.) определяется из состояния двух соседних ячеек на полосе (левой и правой) и собственного состояния, согласно к следующей таблице: \includegraphics{https://static.eolymp.com/content/hl/hlcm8plakl5tbb2o9v43et16o0.gif} Аня выбирает первоначальную конфигурацию ячеек и восхищается получившейся анимацией, которая очень похожа на "Игру жизни" Конвея, с интересным поведением на границе между стабильностью и хаосом. \InputFile Первая строка содержит исходную конфигурацию в виде строки из $16$ символов $0$ и $1$. Все ячейки слева и справа от этой строки считаются $0$. Вторая строка содержит количество $n~(0 \le n < 2^{60})$ шагов, которые необходимо выполнить. Светодиодная лента считается достаточно большой, чтобы ни одна $1$-ячейка никогда не достигла концов ленты. \OutputFile Выведите одно целое число, которое представляет собой общее количество $1$-ячеек в окончательной конфигурации. \Examples Ответ равен $11$, выполнены будут следующие пять шагов: \begin{lstlisting}[language=C++] ...0000000010011011111000... ...0000000110111110001000... ...0000001111100010011000... ...0000011000100110111000... ...0000111001101111101000... ...0001101011111000111000... \end{lstlisting} где все, что не отображается, содержит только $0$-ячейки.