普通的开关

时间限制：$2$ 秒。内存限制：$512$ MB。

题目描述

有 $n+2$ 个开关按编号 $0,1,\ldots,n+1$ 从左到右排列，第 $i$ 个开关的初始状态为 $a_i\in\{0,1\}$。两端的开关 $0,n+1$ 始终保留，其余 $n$ 个开关称为普通开关。

过程共有 $T$ 个时刻。每个时刻选择若干尚未移除的普通开关，允许一个也不选，但任意两个被选开关在当前序列中不能相邻。

每个被选开关根据该时刻开始时的状态发送一次脉冲：状态为 $0$ 时，发给当前紧邻的左侧开关；状态为 $1$ 时，发给当前紧邻的右侧开关。所有脉冲同时到达，接收奇数次脉冲的开关翻转状态，接收偶数次脉冲的开关状态不变。随后同时移除所有被选开关，其余开关重新靠拢。两端开关也会接收脉冲并翻转状态，但不会被移除。

要求第 $T$ 个时刻结束后，所有普通开关均已移除。只要存在一个时刻，所选开关的原编号集合不同，就视为不同的方案。

对于两端开关的四种最终状态 $(0,0),(0,1),(1,0),(1,1)$，分别求合法方案数，答案对 $998244353$ 取模。

输入格式

输入文件：switch.in。

第一行包含两个整数 $n,T$。

第二行包含 $n+2$ 个整数 $a_0,a_1,\ldots,a_{n+1}$。

输出格式

输出文件：switch.out。

输出一行四个整数，依次表示两端开关最终状态为 $(0,0),(0,1),(1,0),(1,1)$ 的方案数对 $998244353$ 取模后的值。

样例

输入：

2 3
0 0 0 0

输出：

3 3 0 0

样例解释

两个普通开关不能同时移除。从三个时刻中选出两个非空时刻，有三种选择。若先移除编号 $1$，再移除编号 $2$，两端最终都为 $0$；若先移除编号 $2$，它的脉冲使编号 $1$ 变为 $1$，随后编号 $1$ 向右发送脉冲，两端最终为 $(0,1)$。两种终态各有三种方案。

附加样例 $\texttt{switch2.in/.ans}$、$\texttt{switch3.in/.ans}$、$\texttt{switch4.in/.ans}$ 分别满足测试点 $3\sim4$、$10\sim13$、$16\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n\le100$，$1\le T<998244353$，$a_i\in\{0,1\}$。