Правило 110#10723
Аня прикрашає свій офіс стильними лампами. Вона використовує довгі світлодіодні стрічки, де кожна комірка вмикається або вимикається щосекунди за простим і елегантним алгоритмом. На кожному кроці стан кожної комірки ( для вимкненої і для увімкненої) визначається на основі стану двох сусідніх комірок (лівої і правої) та власного стану, згідно з наступною таблицею:
Аня обирає початкову конфігурацію комірок і насолоджується анімацією, яка нагадує "Гру життя" Конвея, з цікавою поведінкою на межі між стабільністю і хаосом.
Перший рядок містить початкову конфігурацію у вигляді рядка з символів і . Усі комірки зліва і справа від цього рядка вважаються .
Другий рядок містить кількість n~(0 \le n < 2^{60}) кроків, які потрібно виконати.
Світлодіодна стрічка вважається достатньо великою, щоб жодна -комірка ніколи не досягла кінців стрічки.
Виведіть одне ціле число, яке представляє загальну кількість -комірок у кінцевій конфігурації.
Відповідь дорівнює , виконані будуть наступні п'ять кроків:
...0000000010011011111000...
...0000000110111110001000...
...0000001111100010011000...
...0000011000100110111000...
...0000111001101111101000...
...0001101011111000111000...де все, що не відображається, містить лише -комірки.
Приклад 1