CF1923F Shrink-Reverse

给定一个长度为 $n$ 的二进制字符串 $s$（即由 $n$ 个字符组成，每个字符都是 $0$ 或 $1$）。 我们将 $s$ 看作某个整数的二进制表示，并称该整数为字符串 $s$ 的值。例如，$000$ 的值是 $0$，$01101$ 的值是 $13$，$100000$ 的值是 $32$，以此类推。 你最多可以对 $s$ 执行 $k$ 次操作。每次操作可以是以下两种类型之一： - SWAP：选择 $s$ 中的两个下标 $i < j$，交换 $s_i$ 和 $s_j$； - SHRINK-REVERSE：删除 $s$ 的所有前导零，然后将 $s$ 反转。 例如，对 $000101100$ 执行 SHRINK-REVERSE 操作后，会得到 $001101$。 请问，最多经过 $k$ 次操作后，$s$ 的最小可能值是多少？由于答案可能很大，请输出对 $10^9+7$ 取模的结果。 注意，你需要最小化原始值，而不是最小化取模后的结果。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 5 \times 10^5$，$1 \le k \le n$），分别表示字符串 $s$ 的长度和最多可执行的操作次数。 第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅由 $0$ 和 $1$ 组成。 输入保证 $s$ 至少包含一个 $1$。

输出一个整数，表示经过不超过 $k$ 次操作后，$s$ 的最小可能值。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。 注意，你需要最小化原始值，而不是最小化取模后的结果。

在第一个样例中，一种最优策略如下： 1. $10010010 \xrightarrow{\texttt{SWAP}} 00010110$； 2. $00010110 \xrightarrow{\texttt{SWAP}} 00000111$。 $00000111$ 的值为 $7$。 在第二个样例中，一种最优策略如下： 1. $01101000 \xrightarrow{\texttt{SHRINK}} 1101000 \xrightarrow{\texttt{REVERSE}} 0001011$； 2. $0001011 \xrightarrow{\texttt{SWAP}} 0000111$。 $0000111$ 的值为 $7$。 由 ChatGPT 4.1 翻译