問題文

長さ N の整数列 A = (A_1, \dots, A_N) があります。はじめ、全ての要素は 0 です。

\{(a, b) \, | \, a \in \mathbb{N}, b \in \mathbb{N}, 1 \leq a \leq b \leq N \} の部分集合 S であって、以下の条件を全て満たすものの総数を 998244353 で割った余りを求めてください。

• |S| = M
• S の全ての要素 (l, r) に対して以下を行った後、全ての 1 \leq i \leq N について A_i = B_i が成り立つ。
  • l \leq i \leq r を満たす全ての i に対し、A_i を 1 - A_i で置き換える。

制約

• 1 \leq N \leq 3000
• 1 \leq M \leq \min\left(\frac{N(N + 1)}{2}, 3000\right)
• B_i \in \{0, 1\} \, (1 \leq i \leq N)
• 入力は全て整数である

入力例 1

3 2
1 1 0

出力例 1

2

S = \{(1, 1), (2, 2)\}, \{(1, 3), (3, 3)\} が条件を満たします。

入力例 2

3 1
1 0 1

出力例 2

0

条件を満たす S は存在しません。

入力例 3

10 20
1 0 1 1 0 1 1 1 1 1

出力例 3

71696207