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

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

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

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

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