Тестування схем

Булевий вираз задано. У виразі кожна змінна з'являється рівно один раз. Обчисліть кількість присвоєнь змінних, які роблять вираз істинним.

Вхідні дані

Вхідні дані складаються з одного рядка. Булевий вираз подано у вигляді рядка, що складається з цифр, x, (, ), |, , і  . Інші символи, такі як пробіли, відсутні. Довжина виразу ніколи не перевищує 1,000,000 символів. Граматика виразів визначена наступним BNF.

<вираз> ::= <вираз> "|" <вираз>
         | <вираз> "&" <вираз>
         | "~" <вираз>
         | "(" <вираз> ")"
         | "x" <число>
<число> ::= "1" | "2" | ... | "999999" | "1000000"

Вираз відповідає цій синтаксичній структурі, тому вам не потрібно турбуватися про граматичні помилки. Якщо вираз містить N змінних, кожна змінна з {x1, x2, ..., xN} з'являється рівно один раз.

Вихідні дані

Виведіть рядок, що містить кількість присвоєнь змінних, які роблять вираз істинним, за модулем 1,000,000,007.

Приклади