Вам задана бинарная строка \(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\)?
Выходные данные
Выведите одно целое число — наименьшее возможное значение строки \(s\), которое вы можете получить, применив не более \(k\) операций. Так как ответ может быть слишком большим, выведите его по модулю \(10^{9} + 7\).
Заметим, что вы должны минимизировать само значение, а не его остаток.
Примечание
В первом примере, одна из оптимальных стратегий — следующая:
- 10010010 \(\xrightarrow{\texttt{SWAP}}\) 00010110;
- 00010110 \(\xrightarrow{\texttt{SWAP}}\) 00000111.
Значение строки
00000111 равно
\(7\).
Во втором примере, одна из оптимальных стратегий — следующая:
- 01101000 \(\xrightarrow{\texttt{SHRINK}}\) 1101000 \(\xrightarrow{\texttt{REVERSE}}\) 0001011;
- 0001011 \(\xrightarrow{\texttt{SWAP}}\) 0000111.
Значение строки
0000111 равно
\(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 2
10010010
|
7
|
|
2
|
8 2
01101000
|
7
|
|
3
|
30 30
111111111111111111111111111111
|
73741816
|
|
4
|
14 1
10110001111100
|
3197
|