Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

greedy

hashing

implementation

string suffix structures

strings

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Shrink-Reverse

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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:

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 08:03:25 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|