[AdditionalFile6497.zip](file://AdditionalFile6497.zip?type=additional_file)

#6497. 「雅礼集训 2018 Day1」图

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

有一张 $n$ 个点的图，每个点可以是黑色或者白色，其中一些点已经确定了颜色。

图中一开始没有边，对于每对 $i < j$，你可以从 $i$ 向 $j$ 连一条有向边，也可以不连。

定义交错路为相邻点颜色不同的有向路径，求有多少种情况图中的交错路有奇数或偶数条。两种情况不同当且仅当有节点颜色不同或者有一条边的存在性不同。

输入格式

第一行包括两个正整数 $n, p$。 若 $p = 0$ 表示要求交错路为偶数条，若 $p = 1$ 表示要求交错路为奇数条。

第二行 $n$ 个整数，第 $i$ 个整数若为 $0$，节点 $i$ 为白，若为 $1$，节点 $i$ 为黑，若为 $-1$，节点 $i$ 颜色不确定。

输出格式

输出一个非负整数，表示答案对 $998244353$ 取模后的结果。

样例

输入

3 1
-1 0 1

输出

6

数据范围与提示

对于全部数据， $1 \leq n \leq 2×10^5$。

• 子任务 $\rm 1(points: 10)$：$n \leq 5$
• 子任务 $\rm 2(points: 30)$：$n \leq 50$
• 子任务 $\rm 3(points: 10)$：$n \leq 150$
• 子任务 $\rm 4(points: 15)$：$n \leq 500$
• 子任务 $\rm 5(points: 15)$：$n \leq 5000$
• 子任务 $\rm 6(points: 20)$：无特殊限制