F. Shrink-Reverse
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана бинарная строка $$$s$$$ длины $$$n$$$ (строка, состоящая из $$$n$$$ символов, и каждый символ — либо 0, либо 1).

Посмотрим на строку $$$s$$$ как на двоичное представление некоторого числа, и назовем это число значением строки $$$s$$$. Например, значение строки 000 равно $$$0$$$, значение 01101 равно $$$13$$$, значение 100000 — это $$$32$$$, и так далее.

Вы можете применить не более $$$k$$$ операций к $$$s$$$. Каждая операция должна иметь один из следующих двух типов:

  • SWAP: выбрать два индекса $$$i < j$$$ в $$$s$$$ и поменять местами $$$s_i$$$ и $$$s_j$$$;
  • SHRINK-REVERSE: удалить все лидирующие нули из $$$s$$$ и перевернуть строку $$$s$$$.
Например, после применения SHRINK-REVERSE к строке 000101100 вы получите строку 001101.

Какое минимальное значение строки $$$s$$$ вы можете получить, применив не более $$$k$$$ операций к $$$s$$$?

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 5 \cdot 10^5$$$; $$$1 \le k \le n$$$) — длина строки $$$s$$$ и максимальное количество операций.

Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая из символов 0 и/или 1.

Дополнительное ограничение на входные данные: в строке $$$s$$$ есть хотя бы одна цифра 1.

Выходные данные

Выведите одно целое число — наименьшее возможное значение строки $$$s$$$, которое вы можете получить, применив не более $$$k$$$ операций. Так как ответ может быть слишком большим, выведите его по модулю $$$10^{9} + 7$$$.

Заметим, что вы должны минимизировать само значение, а не его остаток.

Примеры
Входные данные
8 2
10010010
Выходные данные
7
Входные данные
8 2
01101000
Выходные данные
7
Входные данные
30 30
111111111111111111111111111111
Выходные данные
73741816
Входные данные
14 1
10110001111100
Выходные данные
3197
Примечание

В первом примере, одна из оптимальных стратегий — следующая:

  1. 10010010 $$$\xrightarrow{\texttt{SWAP}}$$$ 00010110;
  2. 00010110 $$$\xrightarrow{\texttt{SWAP}}$$$ 00000111.
Значение строки 00000111 равно $$$7$$$.

Во втором примере, одна из оптимальных стратегий — следующая:

  1. 01101000 $$$\xrightarrow{\texttt{SHRINK}}$$$ 1101000 $$$\xrightarrow{\texttt{REVERSE}}$$$ 0001011;
  2. 0001011 $$$\xrightarrow{\texttt{SWAP}}$$$ 0000111.
Значение строки 0000111 равно $$$7$$$.