F. Shrink-Reverse
binary search; brute force; greedy; hashing; implementation; string suffix structures; strings
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\). 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\)?
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.
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.
In the first example, one of the optimal strategies is the following: 10010010 \(\xrightarrow{\texttt{SWAP}}\) 00010110; 00010110 \(\xrightarrow{\texttt{SWAP}}\) 00000111. The value of 00000111 is \(7\).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. The value of 0000111 is \(7\).