← 返回题目列表

AtCoder · nadafes2022_day1_n

N. 范围翻转

中文机器翻译题面 查看原题

配点 : 700 点

問題文

长度 小于或等于 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)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
B_1 \dots B_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