给定一个长度为 $$$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。