Kuro and Topological Parity

题意翻译

给定 $n$ 个点，每个点有黑白两种颜色（如果没有颜色，那么你可以把它任意涂成黑色或白色），同时你可以在这个图上任意加入一些边（当然不能加入重边或自环），要求：加入的边必须从编号小的点指向编号大的点 我们称一条好的路径为经过的点为黑白相间的路径，如果一个图好的路径的总数 $\bmod 2=p$，那么我们称这个图为好的图，现在给定你 $n$ 个点的情况，求这 $n$ 个点能组成的好的图的个数，答案对 $10^9+7$ 取模。 输入格式： 第一行两个整数 $n,p$，分别表示点的个数和 $p$。其中 $n\leq 50$，$p \in \{0,1\}$。 第二行 $n$ 个整数，每个整数只有三种取值：$-1,0,1$。其中，$-1$ 表示这个点未被涂色，你可以随意为他选择一种颜色，$0$ 表示这个点为黑色，$1$ 表示这个点为白色。 输出格式： 一行一个整数，表示答案对 $10^9+7$ 取模的结果

题目描述

Kuro has recently won the "Most intelligent cat ever" contest. The three friends then decided to go to Katie's home to celebrate Kuro's winning. After a big meal, they took a small break then started playing games. Kuro challenged Katie to create a game with only a white paper, a pencil, a pair of scissors and a lot of arrows (you can assume that the number of arrows is infinite). Immediately, Katie came up with the game called Topological Parity. The paper is divided into $ n $ pieces enumerated from $ 1 $ to $ n $ . Shiro has painted some pieces with some color. Specifically, the $ i $ -th piece has color $ c_{i} $ where $ c_{i} = 0 $ defines black color, $ c_{i} = 1 $ defines white color and $ c_{i} = -1 $ means that the piece hasn't been colored yet. The rules of the game is simple. Players must put some arrows between some pairs of different pieces in such a way that for each arrow, the number in the piece it starts from is less than the number of the piece it ends at. Also, two different pieces can only be connected by at most one arrow. After that the players must choose the color ( $ 0 $ or $ 1 $ ) for each of the unpainted pieces. The score of a valid way of putting the arrows and coloring pieces is defined as the number of paths of pieces of alternating colors. For example, $ [1 \to 0 \to 1 \to 0] $ , $ [0 \to 1 \to 0 \to 1] $ , $ [1] $ , $ [0] $ are valid paths and will be counted. You can only travel from piece $ x $ to piece $ y $ if and only if there is an arrow from $ x $ to $ y $ . But Kuro is not fun yet. He loves parity. Let's call his favorite parity $ p $ where $ p = 0 $ stands for "even" and $ p = 1 $ stands for "odd". He wants to put the arrows and choose colors in such a way that the score has the parity of $ p $ . It seems like there will be so many ways which satisfy Kuro. He wants to count the number of them but this could be a very large number. Let's help him with his problem, but print it modulo $ 10^{9} + 7 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ p $ ( $ 1 \leq n \leq 50 $ , $ 0 \leq p \leq 1 $ ) — the number of pieces and Kuro's wanted parity. The second line contains $ n $ integers $ c_{1}, c_{2}, ..., c_{n} $ ( $ -1 \leq c_{i} \leq 1 $ ) — the colors of the pieces.

输出格式

Print a single integer — the number of ways to put the arrows and choose colors so the number of valid paths of alternating colors has the parity of $ p $ .

输入输出样例

输入样例 #1

3 1
-1 0 1

输出样例 #1

6

输入样例 #2

2 1
1 0

输出样例 #2

1

输入样例 #3

1 1
-1

输出样例 #3

2

说明

In the first example, there are $ 6 $ ways to color the pieces and add the arrows, as are shown in the figure below. The scores are $ 3, 3, 5 $ for the first row and $ 5, 3, 3 $ for the second row, both from left to right.