CF413D.2048

The programmers from the R2 company love playing 2048. One day, they decided to invent their own simplified version of this game — 2_k_ on a stripe.

Imagine an infinite in one direction stripe, consisting of unit squares (the side of each square is equal to the height of the stripe). Each square can either be empty or contain some number.

Initially, all squares are empty. Then at infinity one of the unit squares number 2 or 4 appears. Then the player presses a button once, and the appeared number begins to move towards the beginning of the stripe. Let's assume that some number x moves to the beginning of the stripe, then it will stop if:

1. it either gets in the first square of the stripe;
2. or it is in the square that is preceded by a square with number y (y ≠ x). But if number x at some point of time gets to the square with the same number then both numbers add to each other and result in 2_x_. The new number 2_x_ continues moving to the beginning of the stripe by the same rules.

After the final stop of the number moving process, the infinity gets a new number 2 or 4 and the process repeats. Read the notes to the test samples to better understand the moving strategy.

I guess you've understood that the game progress fully depends on the order in which numbers 2 and 4 appear. Let's look at some sequence of numbers 2 and 4 in the game. We assume that the sequence is winning if it results in at least one square getting the number greater or equal than 2_k_.

The goal of the game is to make up a winning sequence of n numbers. But not everything is so simple, some numbers in the sequence are identified beforehand. You are given a sequence consisting of numbers 0, 2, 4. Count how many ways there are to replace each 0 of the sequence with 2 or 4 to get a winning sequence.

R2 公司的程序员们热衷于玩 2048 游戏。某天，他们决定发明一个自己简化版的该游戏——“条带上的 $2_k$”。

想象一条在单方向上无限延伸的条带，由单位正方形组成（每个正方形的边长等于条带的高度）。每个正方形要么为空，要么包含某个数字。

初始时，所有正方形均为空。随后，在条带的无穷远处，会随机出现一个数字 $2$ 或 $4$。接着玩家按一次按钮，该出现的数字便开始向条带起点方向移动。假设某个数字 $x$ 向条带起点移动，则它将在以下任一情形下停止：

1. 它到达了条带的第一个正方形；
2. 它进入了某个正方形，而该正方形前方（更靠近起点一侧）的正方形中已有数字 $y$（其中 $y \ne x$）。
   但若在某一时刻，数字 $x$ 移动到了一个含有相同数字 $x$ 的正方形中，则这两个数字将相加，合并为 $2x$。新生成的数字 $2x$ 将继续按照相同的规则向条带起点方向移动。

当该数字的移动过程最终停止后，条带无穷远处又会出现一个新的数字 $2$ 或 $4$，整个过程重复进行。请参阅测试样例的注释以更清晰地理解上述移动策略。

想必你已理解：游戏的进程完全取决于数字 $2$ 和 $4$ 出现的顺序。我们考察游戏中某个由 $2$ 和 $4$ 构成的序列。若该序列能使得至少一个正方形中出现不小于 $2_k$ 的数字，则称该序列为获胜序列。

本游戏的目标是构造一个长度为 $n$ 的获胜序列。但事情并不那么简单——序列中部分位置的数字已被预先确定。你将获得一个由数字 $0$、$2$、$4$ 组成的序列。请计算：有多少种方式将序列中每个 $0$ 替换为 $2$ 或 $4$，使得最终得到的序列是一个获胜序列？

The first line contains two integers n and k (1 ≤ n ≤ 2000; 3 ≤ k ≤ 11). The next line contains sequence of n integers, each of them is either 0, or 2, or 4.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2000$；$3 \leq k \leq 11$）。下一行包含一个由 $n$ 个整数组成的序列，每个整数均为 $0$、$2$ 或 $4$。

Print a single integer — the number of ways to replace zeroes by numbers 2 or 4 to get a winning sequence. As this number can be rather large, print it modulo 1000000007 (109 + 7).

输出一个整数——即用数字 2 或 4 替换所有零，从而得到一个获胜序列的方案数。由于该数可能非常大，请对 $1000000007$（即 $10^9 + 7$）取模后输出。

Consider the first example. The beginning of the strip will look as follows:

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

To better understand the game, you can see the original game on http://gabrielecirulli.github.io/2048/. Please note that the game that is described on the strip is slightly different from the original game (when the two numbers add up in the original game, they do not keep moving). Be careful, the game is addictive, there isn't much time for the contest!

考虑第一个例子。纸条的开头部分如下所示：

2  →  4  →  8  →  8 2  →  8 4  →  8 4 2  →  16。

为了更好地理解该游戏，您可访问原始游戏网址：http://gabrielecirulli.github.io/2048/。请注意，本题中描述的纸条上的游戏与原始游戏略有不同（在原始游戏中，当两个数字相加后，它们将不再继续移动）。请小心，该游戏极易上瘾，而比赛时间所剩无几！