311030: CF1923F. Shrink-Reverse
Description
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 < j$ in $s$ and swap $s_i$ with $s_j$;
- SHRINK-REVERSE: delete all leading zeroes from $s$ and reverse $s$.
What is the minimum value of $s$ you can achieve by performing at most $k$ operations on $s$?
InputThe 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.
OutputPrint 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.
ExamplesInput8 2 10010010Output
7Input
8 2 01101000Output
7Input
30 30 111111111111111111111111111111Output
73741816Input
14 1 10110001111100Output
3197Note
In the first example, one of the optimal strategies is the following:
- 10010010 $\xrightarrow{\texttt{SWAP}}$ 00010110;
- 00010110 $\xrightarrow{\texttt{SWAP}}$ 00000111.
In the second example, one of the optimal strategies is the following:
- 01101000 $\xrightarrow{\texttt{SHRINK}}$ 1101000 $\xrightarrow{\texttt{REVERSE}}$ 0001011;
- 0001011 $\xrightarrow{\texttt{SWAP}}$ 0000111.
Output
输入数据格式：第一行包含两个整数n和k，分别表示字符串s的长度和最大操作次数。第二行包含长度为n的字符串s，由字符'0'和'1'组成。
输出数据格式：打印一个整数，即通过不超过k次操作后s可以达到的最小值，结果对10^9 + 7取模。
例如，对于输入：
```
8 2
10010010
```
输出应为：
```
7
```
对于输入：
```
30 30
111111111111111111111111111111
```
输出应为：
```
73741816
```题目大意：给定一个长度为n的由字符'0'和'1'组成的二进制字符串s，你可以对s进行最多k次操作。每次操作有两种类型：SWAP和SHRINK-REVERSE。SWAP操作是选择s中的两个索引i < j，并交换s_i和s_j；SHRINK-REVERSE操作是删除s的所有前导零并反转s。你需要找到通过最多k次操作后s可以达到的最小值。 输入数据格式：第一行包含两个整数n和k，分别表示字符串s的长度和最大操作次数。第二行包含长度为n的字符串s，由字符'0'和'1'组成。 输出数据格式：打印一个整数，即通过不超过k次操作后s可以达到的最小值，结果对10^9 + 7取模。 例如，对于输入： ``` 8 2 10010010 ``` 输出应为： ``` 7 ``` 对于输入： ``` 30 30 111111111111111111111111111111 ``` 输出应为： ``` 73741816 ```