F. Shrink-Reverse
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$?

Input

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.

Output

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.

Examples
Input
8 210010010
Output
7

Input
8 201101000
Output
7

Input
30 30111111111111111111111111111111
Output
73741816

Input
14 110110001111100
Output
3197

Note

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$.