Qayda 110

Aynur ofisini ən gözəl lampalarla bəzəyir. O, hər bir hüceyrənin hər saniyə sadə və gözəl bir alqoritmə əsasən yandırıldığı və ya söndürüldüyü uzun LED lentlərdən istifadə edir. Hər addımda hər bir hüceyrənin vəziyyəti (söndürülmüş üçün $0$, yandırılmış üçün $1$) lentdəki iki qonşu hüceyrənin (sol və sağ) və öz vəziyyətinə əsasən aşağıdakı cədvələ uyğun olaraq müəyyən edilir:

Aynur hüceyrələrin ilkin konfiqurasiyasını seçir və Konveyin "Həyat Oyunu"na bənzəyən, sabitlik və xaos arasında maraqlı davranış sərgiləyən animasiyaya heyran qalır.

Giriş verilənləri

Birinci sətir $16$ simvoldan ibarət $0$ və $1$-lərdən ibarət olan ilkin konfiqurasiyanı ehtiva edir. Bu sətirin solunda və sağında olan bütün hüceyrələr $0$ hesab edilir.

İkinci sətir $n(0\le n<2^{60})$ addım sayını ehtiva edir.

LED lent kifayət qədər böyük hesab edilir ki, heç bir $1$-hüceyrə heç vaxt lentin sonuna çatmasın.

Çıxış verilənləri

Son konfiqurasiyada olan ümumi $1$-hüceyrələrin sayını təmsil edən bir tam ədəd çıxarın.

Nümunələr

Cavab $11$-dir, aşağıdakı beş addım yerinə yetiriləcəkdir:

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

burada göstərilməyən hər şey yalnız $0$-hüceyrələrdən ibarətdir.