Задача . D. 2048

Программисты компании R2 любят играть в 2048. Как-то раз они решили изобрести собственную упрощенную модификацию этой игры — 2^k на полоске.

Представьте бесконечную в одну сторону полоску, состоящую из единичных квадратов (сторона каждого равна высоте полоски). Каждый квадрат может быть пустой, а может содержать некоторое число.

Изначально все квадраты пустые. Затем в бесконечности на одном из единичных квадратов появляется число 2, либо 4. После чего игрок один раз нажимает на кнопку, и появившееся число начинает двигаться в сторону начала полоски. Пусть некоторое число x движется к началу полоски, тогда оно остановится, если:

1. либо оно окажется в первом квадрате полоски;
2. либо оно окажется в квадрате, перед которым находится квадрат с числом y (y ≠ x). Если же число x в какой-то момент времени окажется в квадрате с таким же числом, то два числа сложатся и превратятся в одно число 2x. Новое число 2x по тем же правилам продолжит двигаться в сторону начала полоски.

После окончательной остановки процесса передвижения чисел, в бесконечности появляется новое число 2 или 4, и все повторяется. Чтобы лучше понять процесс передвижения прочитайте пояснения к тестовым примерам.

Наверное, вы уже поняли, что ход игры целиком и полностью завит от того, в какой последовательности появляются 2 и 4 в игре. Рассмотрим некоторую последовательность, в которой появляются 2 и 4 в игре. Считается, что эта последовательность победная, если в результате нее хотя бы в одном квадрате появится число не менее 2^k.

Смысл игры состоит в том, чтобы составить победную последовательность из n чисел. Но не все так просто, некоторые числа последовательности определены заранее. Задана последовательность, состоящая из чисел 0, 2, 4. Посчитайте, сколько существует способов заменить каждый 0 этой последовательности на 2 или 4, чтобы получить победную последовательность.