Problem Statement

There are $N$ tiles with distinguishable front and back sides, called tiles $1,2,...,N$. Initially, all tiles are face up. You will now perform the following operation $M$ times.

• Choose positive integers $L,R$ satisfying $1 \leq L \leq R \leq N$, and flip all tiles $i\,(L\leq i \leq R)$.

Let $L_i, R_i$ be the $L, R$ chosen in the $i\,(1 \le i \le M)$-th operation, respectively.

There are $(\frac{N(N+1)}{2})^M$ operation sequences $((L_i, R_i))_{i = 1, \cdots, M}$. Among them, find the number, modulo $998244353$, of operation sequences such that the state of the tiles after all operations is $A_1,A_2,...,A_N$.

Here, $A_i = 0$ means that tile $i$ is face up, and $A_i = 1$ means that tile $i$ is face down.

Constraints

• $1 \leq N \leq 5000$
• $0 \leq M \leq 5000$
• $0 \leq A_i \leq 1$
• All inputs are integers

Input

$N\ M\\A_1\ A_2 \cdots A_N$

Output

Output the answer modulo $998244353$. Print a newline at the end.

Sample

4 2
0 1 1 0

6

1 56
1

0

15 121
1 0 1 1 0 0 0 1 0 0 1 1 1 0 1

255247577