← 返回题目列表

Codeforces · 1923/F

F. 收缩-反向

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

给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ (由 $$$n$$$ 个字符组成的字符串,每个字符要么是 0 要么是 1)。

让我们将 $$$s$$$ 视为某个整数的二进制表示形式,并将该整数命名为字符串 $$$s$$$ 的值。例如,000 的值为 $$$0$$$,01101 的值为 $$$13$$$,“100000”的值为 $$$32$$$ 等等。

您最多可以对 $$$s$$$ 执行 $$$k$$$ 操作。每个操作应具有以下两种类型之一:

- 交换:在$$$s$$$中选择两个索引$$$i < j$$$,并将$$$s_i$$$与$$$s_j$$$交换;
- SHRINK-REVERSE:删除 $$$s$$$ 中的所有前导零并反转 $$$s$$$。

通过对 $$$s$$$ 执行最多 $$$k$$$ 操作可以获得的 $$$s$$$ 的最小值是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5 \cdot 10^5$$$; $$$1 \le k \le n$$$) — 字符串 $$$s$$$ 的长度和最大操作次数。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。

输入的附加约束:$$$s$$$ 至少包含一个 1。

输出

打印单个整数 - 使用不超过 $$$k$$$ 运算可以实现的 $$$s$$$ 的最小值。由于答案可能太大,请打印它对 $$$10^{9} + 7$$$ 取模。

请注意,您需要最小化原始值,而不是余数。

示例

输入 #1

8 2
10010010

输出 #1

7

输入 #2

8 2
01101000

输出 #2

7

输入 #3

30 30
111111111111111111111111111111

输出 #3

73741816

输入#4

14 1
10110001111100

输出#4

3197

注意

在第一个示例中,最佳策略之一如下:

1. 10010010 $$$\xrightarrow{\texttt{SWAP}}$$$ 00010110;
2. 00010110 $$$\xrightarrow{\texttt{SWAP}}$$$ 00000111。

在第二个示例中,最佳策略之一如下:

1. 01101000 $$$\xrightarrow{\texttt{收缩}}$$$ 1101000 $$$\xrightarrow{\texttt{反向}}$$$ 0001011;
2. 0001011 $$$\xrightarrow{\texttt{SWAP}}$$$ 0000111。