D. 2048
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

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

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

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

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

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

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

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

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

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 2000; 3 ≤ k ≤ 11). В следующей строке записана последовательность из n целых чисел, каждое из которых: либо 0, либо 2, либо 4.

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

Выведите единственное целое число — количество способов заменить нули на 2 или 4, чтобы получить победную последовательность. Так как это количество может быть достаточно большим, выведите его остаток от деления на 1000000007 (109 + 7).

Примеры
Входные данные
7 4
2 2 4 2 2 2 2
Выходные данные
1
Входные данные
1 3
0
Выходные данные
0
Входные данные
2 3
0 4
Выходные данные
1
Входные данные
5 4
2 0 0 4 4
Выходные данные
2
Примечание

Рассмотрим первый тестовый пример. Начало полоски будет трансформироваться следующим образом:

2  →  4  →  8  →  8 2  →  8 4  →  8 4 2  →  16.

Чтобы лучше понять процесс игры, можете посмотреть оригинальную игру на http://gabrielecirulli.github.io/2048/. Обратите внимание, что описанная игра на полоске немного отличается от оригинальной (когда два числа складываются в оригинальной игре, они не продолжают двигаться). Будьте осторожны, игра затягивает, а времени на контесте не так много!