Тестирование схем

Дано булевое выражение, в котором каждая переменная встречается ровно один раз. Необходимо определить количество наборов значений переменных, при которых выражение будет истинным.

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

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

<выражение>::=<выражение> "|" <выражение>
<выражение>::=<выражение> "&" <выражение>
<выражение>::="~" <выражение> | "(" <выражение> ")"
<выражение>::="x"
<цифра>::="1" | "2" |... | "999999" | "1000000"

Выражение соответствует указанной грамматике, поэтому грамматические ошибки исключены. Если в выражении N переменных, каждая из них ({x1, x2, ..., xN}) встречается ровно один раз.

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

Выведите количество наборов значений переменных, при которых выражение истинно, по модулю 1,000,000,007.

Примеры