問題文

$N$ 枚の表裏が区別できるタイルがあり、タイル $1,2,...,N$ と呼びます。はじめタイルは全て表向きです。 これから次の操作を $M$ 回行います。

• $1 \leq L \leq R \leq N$ を満たす正の整数 $L,R$ を選び、タイル $i\,(L\leq i \leq R)$ を全てひっくり返す。

$i\,(1 \le i \le M)$ 回目の操作で選んだ $L, R$ をそれぞれ $L_i, R_i$ とします。

操作列 $((L_i, R_i))_{i = 1, \cdots, M}$ は $(\frac{N(N+1)}{2})^M$ 通りありますが、そのうち、操作を終えた後のタイルの状態が $A_1,A_2,...,A_N$ となる操作列の個数を $998244353$ で割ったあまりを求めてください。

ここで、 $A_i = 0$ のときタイル $i$ が表、 $A_i = 1$ のときタイル $i$ が裏であることを表します。

制約

• $1 \leq N \leq 5000$
• $0 \leq M \leq 5000$
• $0 \leq A_i \leq 1$
• 入力はすべて整数

入力

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

出力

答えを $998244353$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

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