A. Танцевальный клуб Малека
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

По традиции, каждый год перед международной олимпиадой по информатике все участники фан-клуба Наталии приглашаются в танц-клуб Малека для приятного времяпрепровождения. Танц-клуб Малека насчитывает 2n участников и по совпадению, фан-клуб Наталии также насчитывает 2n участников. Каждому участнику ТКМ приписывается уникальный номер i от 0 до 2n - 1. То же самое верно для каждого участника ФКН.

Среди прочего, встречи традиционно включают парный танец, где каждый участник ТКМ танцует с участником ФКН. Пара в танце — это такая пара чисел (a, b), что участник номер a из ТКМ танцует с участником номер b из ФКН.

Назовем сложностью распределения пар количество пар танцующих пар (a, b) и (c, d), таких, что a < c и b > d.

Вам дано двоичное число x длины n. Мы знаем, что участник номер i из ТКМ танцует с участником номер из ФКН. Ваша задача — высчитать сложность такого распределения по модулю 1000000007 (109 + 7).

Выражение обозначает применение операции «XOR» к числам x и y. Данная операция существует во всех современных языках программирования. Например, в C++ и Java она обозначается как «^», в языке Pascal — как «xor».

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

В первой строке содержится двоичное число x длины n, (1 ≤ n ≤ 100).

Это число может содержать ведущие нули.

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

Выведите сложность данного распределения по модулю 1000000007 (109 + 7).

Примеры
Входные данные
11
Выходные данные
6
Входные данные
01
Выходные данные
2
Входные данные
1
Выходные данные
1