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:
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.
8 210010010
7
8 201101000
7
30 30111111111111111111111111111111
73741816
14 110110001111100
3197
In the first example, one of the optimal strategies is the following:
In the second example, one of the optimal strategies is the following:
Name |
---|