English · Original
Chinese · Translation
Formal · Original
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$.
## Input
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.
## Output
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$.
[samples]
## Note
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.
<center></center>
Kuro 最近赢得了 "史上最聪明的猫" 比赛。三位朋友决定去 Katie 的家庆祝 Kuro 的胜利。在享用了一顿丰盛的餐食后，他们稍作休息，开始玩游戏。
Kuro 挑战 Katie 用一张白纸、一支铅笔、一对剪刀和大量箭头（你可以假设箭头数量是无限的）设计一个游戏。Katie 立刻想出了一个名为 _Topological Parity_ 的游戏。
这张纸被划分为 $n$ 个编号从 $1$ 到 $n$ 的部分。Shiro 已经用某种颜色涂了一些部分。具体来说，第 $i$ 个部分的颜色为 $c_i$，其中 $c_i = 0$ 表示黑色，$c_i = 1$ 表示白色，$c_i = -1$ 表示该部分尚未上色。
游戏规则很简单。玩家必须在某些不同部分之间放置一些箭头，使得每条箭头都从编号较小的部分指向编号较大的部分。此外，任意两个不同的部分之间最多只能有一条箭头。之后，玩家必须为每个未上色的部分选择一个颜色（$0$ 或 $1$）。一种有效的箭头放置和着色方案的得分定义为交替颜色路径的数量。例如，$[ 1 arrow.r 0 arrow.r 1 arrow.r 0 ]$、$[ 0 arrow.r 1 arrow.r 0 arrow.r 1 ]$、$[ 1 ]$、$[ 0 ]$ 都是有效的路径并会被计数。你只能从部分 $x$ 移动到部分 $y$，当且仅当存在一条从 $x$ 到 $y$ 的箭头。
但 Kuro 还不够有趣。他热爱奇偶性。我们称他喜欢的奇偶性为 $p$，其中 $p = 0$ 表示 "偶数"，$p = 1$ 表示 "奇数"。他希望放置箭头并选择颜色，使得得分具有 $p$ 的奇偶性。
似乎有非常多的方式可以满足 Kuro 的要求。他想计算满足条件的方式数量，但这可能是一个非常大的数字。请帮助他解决这个问题，但结果请对 $10^9 + 7$ 取模。
第一行包含两个整数 $n$ 和 $p$ ($1 lt.eq n lt.eq 50$, $0 lt.eq p lt.eq 1$) —— 部分的数量和 Kuro 所需的奇偶性。
第二行包含 $n$ 个整数 $c_1, c_2,..., c_n$ ($-1 lt.eq c_i lt.eq 1$) —— 各部分的颜色。
输出一个整数 —— 放置箭头并选择颜色，使得交替颜色路径数量具有奇偶性 $p$ 的方案数。
## Input
第一行包含两个整数 $n$ 和 $p$ ($1 lt.eq n lt.eq 50$, $0 lt.eq p lt.eq 1$) —— 部分的数量和 Kuro 所需的奇偶性。第二行包含 $n$ 个整数 $c_1, c_2,..., c_n$ ($-1 lt.eq c_i lt.eq 1$) —— 各部分的颜色。
## Output
输出一个整数 —— 放置箭头并选择颜色，使得交替颜色路径数量具有奇偶性 $p$ 的方案数。
[samples]
## Note
在第一个例子中，有 $6$ 种为部分上色和添加箭头的方式，如下面的图所示。第一行的得分依次为 $3, 3, 5$，第二行的得分依次为 $5, 3, 3$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of pieces, labeled $ 1 $ to $ n $.
Let $ c = (c_1, c_2, \dots, c_n) \in \{-1, 0, 1\}^n $ be the color vector, where:
- $ c_i = 0 $: piece $ i $ is black,
- $ c_i = 1 $: piece $ i $ is white,
- $ c_i = -1 $: piece $ i $ is uncolored.
Let $ U = \{ i \in \{1, \dots, n\} \mid c_i = -1 \} $ be the set of uncolored pieces.
Let $ F = \{1, \dots, n\} \setminus U $ be the set of fixed-color pieces.
An **arrow configuration** is a subset $ E \subseteq \{ (i,j) \mid 1 \le i < j \le n \} $, representing directed edges from lower-indexed to higher-indexed pieces.
A **coloring extension** is a function $ \chi: U \to \{0,1\} $ assigning colors to uncolored pieces.
Define the **coloring assignment** $ \tilde{c} \in \{0,1\}^n $ as:
$$
\tilde{c}_i =
\begin{cases}
c_i & \text{if } c_i \ne -1, \\
\chi(i) & \text{if } c_i = -1.
\end{cases}
$$
A **valid path** is a non-empty sequence of distinct pieces $ (v_1, v_2, \dots, v_k) $ such that:
- $ v_1 < v_2 < \dots < v_k $,
- $ (v_i, v_{i+1}) \in E $ for all $ i \in \{1, \dots, k-1\} $,
- $ \tilde{c}_{v_i} \ne \tilde{c}_{v_{i+1}} $ for all $ i \in \{1, \dots, k-1\} $.
Let $ S(E, \tilde{c}) $ denote the total number of valid paths under arrow set $ E $ and coloring $ \tilde{c} $.
**Constraints**
1. $ 1 \le n \le 50 $
2. $ p \in \{0,1\} $
3. $ c_i \in \{-1, 0, 1\} $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of pairs $ (E, \chi) $ such that:
$$
S(E, \tilde{c}) \equiv p \pmod{2}
$$
modulo $ 10^9 + 7 $.
API Response (JSON)
{
"problem": {
"name": "E. Kuro and Topological Parity",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF979E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Kuro 最近赢得了 \"史上最聪明的猫\" 比赛。三位朋友决定去 Katie 的家庆祝 Kuro 的胜利。在享用了一顿丰盛的餐食后，他们稍作休息，开始玩游戏。\n\nKuro 挑战 Katie 用一张白纸、一支铅笔、一对剪刀和大量箭头（你可以假设箭头数量是无限的）设计一个游戏。Katie 立刻想出了一个名为 _Topological Parity_ 的游戏。\n\n这张纸被划分为 $n$ 个编号从 $1$ ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of pieces, labeled $ 1 $ to $ n $. \nLet $ c = (c_1, c_2, \\dots, c_n) \\in \\{-1, 0, 1\\}^n $ be the color vector, where: \n- $ c_i = 0 $: piece...",
"is_translate": false,
"language": "Formal"
}
]
}