题目描述

我是杨雅兰，我喜欢出阴间 Round。 $\color{white}{orz \ zsq}$

你现在要做一个计算问题。 $\color{white}{orz \ zsq}$

在一条直线上有 $N$ 个粒子，初始分别在 $1, 2, ... , N$ 处，在 $1$ 和 $N$ 处各有一堵墙。 $\color{white}{orz \ zsq}$

每个粒子初始时向左或向右以 $1 m/s$ 的速度运动。 $\color{white}{orz \ zsq}$

粒子碰到墙时会立即改为向相反方向运动。 $\color{white}{orz \ zsq}$

两个粒子相遇时，有 $p$ 的概率左边的粒子会消失，有 $1 − p$ 的概率右边的粒子会消失。 $\color{white}{orz \ zsq}$

试求最后 $N$ 号粒子存活下来的概率。 $\color{white}{orz \ zsq}$

输入格式

第一行一个正整数 $N$，和一个整数 $p$ 代表真实的概率在模 $998244353$ 意义下的值。

第二行 $N$ 个为 $0$ 或 $1$ 的整数，如果是 $0$ 那么初始向左，是 $1$ 则初始向右。

输出格式

一行一个整数表示答案模 $998244353$ 意义下的值。

样例 $1$ 输入

3 332748118
1 1 1

样例 $1$ 输出

443664157

样例 $2$ 输入

5 332748118
1 0 1 0 1

样例 $2$ 输出

406692144

样例 $3$ 输入

92 303676146
0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 1

样例 $3$ 输出

825426494

数据规模与约定

对于 $20\%$ 的数据，满足 $2 \leq N \leq 20$。

对于 $40\%$ 的数据，满足 $2 \leq N \leq 100$。

对于另外 $20\%$ 的数据，满足所有粒子初始时都向同一方向走。

对于 $100\%$ 的数据，满足 $2 \leq N \leq 10^3$。