CF413D 2048

R2公司的程序员们非常喜欢玩 2048 游戏。一天，他们决定发明一个简化版的游戏——“$2^{k}$ 条带版”。 想象有一个单向无限延伸的条带，由若干单位正方形组成（每个正方形的边长等于条带的高度）。每个正方形要么是空的，要么包含某个数字。 最开始，所有的正方形都是空的。随后，在最远端的某个位置出现了一个数字 $2$ 或 $4$。接下来，玩家只需按下一次按钮，出现的数字就会开始朝条带的起点移动。假设某个数字 $x$ 正在向条带起点靠近，它会在以下任一情况下停止： 1. 它到达了条带的第一个正方形； 2. 或者它到达某个格子，且该格子的前一个格子中有一个与它不同的数字 $y$（即 $y \neq x$）。但如果 $x$ 此时遇到了与自己相同的数字，那么它们会合并为一个 $2x$。新产生的 $2x$ 会继续朝起点方向移动，规则相同。 当数字最终停止移动后，最远端会再出现一个新的数字 $2$ 或 $4$，游戏流程重复此过程。为了便于理解移动规则，请参考测试样例的注释。 相信你已经明白了，这个游戏的进展完全取决于数字 $2$ 和 $4$ 出现的顺序。现在，给定一组 $2$ 和 $4$ 的序列，如果至少有一个格子中的数字达到或超过 $2^{k}$，我们称这个序列是“获胜序列”。 游戏的目标是构造一个长度为 $n$ 的获胜序列。但事情没那么简单，序列中的一些数字已经被预先指定。你会得到一个长度为 $n$ 的序列，序列中的每个数字为 $0$、$2$ 或 $4$。 你的任务是统计有多少种方法可以将所有的 $0$ 替换为 $2$ 或 $4$，并使得最终得到一个获胜序列。

第一行包含两个整数 $n$ 和 $k$，满足 $1 \leq n \leq 2000$，$3 \leq k \leq 11$。 第二行包含 $n$ 个整数，每个整数是 $0$、$2$ 或 $4$，表示初始序列。

输出一个整数，表示有多少种将 $0$ 替换为 $2$ 或 $4$ 的方案，使得最终得到一个获胜序列。答案对 $1000000007$（$10^9+7$）取模。

以第一个样例说明为例，条带开头的状态演变如下： 2 $\to$ 4 $\to$ 8 $\to$ 8 2 $\to$ 8 4 $\to$ 8 4 2 $\to$ 16。 为了深入理解本游戏，可以参考原版 2048 游戏：https://gabrielecirulli.github.io/2048/。请注意，本题描述的条带游戏与原版有所不同（合并后数字会继续移动），请仔细阅读规则。小心，游戏很容易让人上瘾，比赛时间有限！ 由 ChatGPT 5 翻译