← 返回题目列表

Codeforces · 413/D

D. 2048游戏

中文机器翻译题面 查看原题

来自 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/上查看原版游戏。请注意,条上描述的游戏与原始游戏略有不同(当原始游戏中的两个数字相加时,它们不会继续移动)。小心,游戏很容易上瘾,比赛的时间不多了!