来自 R2 公司的程序员喜欢玩 2048。有一天,他们决定发明这个游戏的简化版本——2k on a strip。
想象一个无限单向条纹,由单位正方形组成(每个正方形的边长等于条纹的高度)。每个方块可以是空的,也可以包含一些数字。
最初,所有方块都是空的。然后在无穷远处出现单位方格数字 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) 取模。
示例
输入 #1
7 4 2 2 4 2 2 2 2
输出 #1
1
输入 #2
1 3 0
输出 #2
0
输入 #3
2 3 0 4
输出 #3
1
输入#4
5 4 2 0 0 4 4
输出#4
2
注意
考虑第一个例子。该条带的开头如下所示:
2 → 4 → 8 → 8 2 → 8 4 → 8 4 2 → 16.
为了更好地了解游戏,您可以在http://gabrielecirulli.github.io/2048/上查看原版游戏。请注意,条上描述的游戏与原始游戏略有不同(当原始游戏中的两个数字相加时,它们不会继续移动)。小心,游戏很容易上瘾,比赛的时间不多了!