По традиции, каждый год перед международной олимпиадой по информатике все участники фан-клуба Наталии приглашаются в танц-клуб Малека для приятного времяпрепровождения. Танц-клуб Малека насчитывает 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».