CF1923F.Shrink-Reverse

You are given a binary string $s$ of length $n$ (a string consisting of $n$ characters, and each character is either 0 or 1).

Let's look at $s$ as at a binary representation of some integer, and name that integer as the value of string $s$. For example, the value of 000 is $0$, the value of 01101 is $13$, "100000" is $32$ and so on.

You can perform at most $k$ operations on $s$. Each operation should have one of the two following types:

• SWAP: choose two indices $i \lt j$ in $s$ and swap $s_i$ with $s_j$;
• SHRINK-REVERSE: delete all leading zeroes from $s$ and reverse $s$.

For example, after you perform SHRINK-REVERSE on 000101100, you'll get 001101.

What is the minimum value of $s$ you can achieve by performing at most $k$ operations on $s$?

给你一个长度为 $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$ 达到的最小可能值是多少？

The first line contains two integers $n$ and $k$ ($2 \le n \le 5 \cdot 10^5$; $1 \le k \le n$) — the length of the string $s$ and the maximum number of operations.

The second line contains the string $s$ of length $n$ consisting of characters 0 and/or 1.

Additional constraint on the input: $s$ contains at least one 1.

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 5 \cdot 10^5$；$1 \le k \le n$）—— 分别表示字符串 $s$ 的长度以及操作次数上限。

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

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

Print a single integer — the minimum value of $s$ you can achieve using no more than $k$ operations. Since the answer may be too large, print it modulo $10^{9} + 7$.

Note that you need to minimize the original value, not the remainder.

输出一个整数——在最多使用 $k$ 次操作的前提下，你能达到的 $s$ 的最小值。由于答案可能过大，请对 $10^{9} + 7$ 取模后输出。

注意：你需要最小化的是原始值，而非其取模后的余数。

In the first example, one of the optimal strategies is the following:

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

The value of 00000111 is $7$.

In the second example, one of the optimal strategies is the following:

1. 01101000 $\xrightarrow{\texttt{SHRINK}}$ 1101000 $\xrightarrow{\texttt{REVERSE}}$ 0001011;
2. 0001011 $\xrightarrow{\texttt{SWAP}}$ 0000111.

The value of 0000111 is $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$。