← 返回题目列表

Codeforces · 979/E

E. Kuro 和拓扑奇偶校验

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

Kuro 最近赢得了“有史以来最聪明的猫”竞赛。三个朋友随后决定去凯蒂的家庆祝库罗的获胜。饱餐一顿后,他们稍事休息,然后开始玩游戏。

Kuro 向 Katie 提出挑战,要求她制作一个游戏,只需要一张白纸、一支铅笔、一把剪刀和很多箭头(你可以假设箭头的数量是无限的)。凯蒂立即想出了一个名为“拓扑奇偶校验”的游戏。

论文分为 $$$n$$$ 个部分,从 $$$1$$$ 到 $$$n$$$ 列举。 Shiro给一些作品涂上了一些颜色。具体来说,第 $$$i$$$ 块的颜色为 $$$c_{i}$$$,其中 $$$c_{i} = 0$$$ 定义黑色,$$$c_{i} = 1$$$ 定义白色,$$$c_{i} = -1$$$ 表示该块尚未着色。

游戏规则很简单。玩家必须在几对不同的棋子之间放置一些箭头,使得对于每个箭头,其起始棋子的编号小于其结束棋子的编号。另外,两个不同的棋子最多只能用一根箭头连接。之后,玩家必须为每个未上色的棋子选择颜色($$$0$$$ 或 $$$1$$$)。放置箭头和着色片的有效方式的分数被定义为交替颜色的片的路径数。例如,$$$[1 \to 0 \to 1 \to 0]$$$、$$$[0 \to 1 \to 0 \to 1]$$$、$$$[1]$$$、$$$[0]$$$ 是有效路径,将被计数。当且仅当存在从 $$$x$$$ 到 $$$y$$$ 的箭头时,您才可以从 $$$x$$$ 前往 $$$y$$$。

但是 Kuro 还不好玩。他喜欢平等。我们称他最喜欢的奇偶校验为 $$$p$$$,其中 $$$p = 0$$$ 代表“偶数”,$$$p = 1$$$ 代表“奇数”。他希望以这样的方式放置箭头并选择颜色,使分数具有 $$$p$$$ 的平价性。

看来有很多方法可以让Kuro满意。他想要数一下他们的数量,但这可能是一个非常大的数字。让我们帮助他解决问题,但打印它对 $$$10^{9} + 7$$$ 取模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$p$$$ ($$$1 \leq n \leq 50$$$, $$$0 \leq p \leq 1$$$) — 棋子的数量和 Kuro 想要的奇偶校验。

第二行包含 $$$n$$$ 整数 $$$c_{1}, c_{2}, ..., c_{n}$$$ ($$$-1 \leq c_{i} \leq 1$$$) — 棋子的颜色。

输出

打印一个整数 - 放置箭头和选择颜色的方式数量,以便交替颜色的有效路径数量具有 $$$p$$$ 奇偶校验。

示例

输入 #1

3 1
-1 0 1

输出 #1

6

输入 #2

2 1
1 0

输出 #2

1

输入 #3

1 1
-1

输出 #3

2

注意

在第一个示例中,有 $$$6$$$ 种颜色和添加箭头的方法,如下图所示。第一行的分数为 $$$3, 3, 5$$$,第二行的分数为 $$$5, 3, 3$$$(从左到右)。