配点 : 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