当前没有测试数据。

题目描述

给定一个长度为 $n$ 的字符串 $s$，其中每个字符是 $0$、$1$ 或 $?$。你需要把每个 $?$ 独立替换为 $0$ 或 $1$。

一个非空二进制字符串的一个“段”是一个极长的、字符全部相同的连续子串。例如，$0011100$ 依次包含长度为 $2,3,2$ 的三个段。

替换完成后的字符串需要满足：

1. 恰好包含 $k$ 个段；
2. 每个全为 $0$ 的段长度都在 $[L_0, R_0]$ 内；
3. 每个全为 $1$ 的段长度都在 $[L_1, R_1]$ 内。

求合法替换方案数，对 $998244353$ 取模。

输入格式

第一行六个整数 $n, k, L_0, R_0, L_1, R_1$。

第二行一个长度为 $n$ 的字符串 $s$。

输出格式

输出一个整数，表示合法替换方案数对 $998244353$ 取模的结果。

样例

5 3 1 2 1 3
?0??1

2

样例解释 两种合法结果为 10011 和 10111。

数据规模与约定

• $1 \le n \le 3000$；
• $1 \le k \le n$；
• $1 \le L_0 \le R_0 \le n$；
• $1 \le L_1 \le R_1 \le n$；
• $s$ 仅包含 $0$、$1$、$?$；

共 20 个测试点，每个测试点 5 分。下表各行所列测试点共同满足对应的额外约束。

原题链接

原题链接