Migrated from Lutece 845 方师傅学数字逻辑

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

方师傅这学期开始学习数字逻辑。

在课上，老师提出了一个问题，给你一个逻辑表达式，里面的每个变量都只出现一次。你可以随意选择每个变量是$0$还是$1$，问最终表达式的值为$1$的选择方案共有多少种。

方师傅很弱啊，于是他来问你了，你能帮助他么？

Input

每组数据包含$1$行，是$1$个字符串，代表老师给出的逻辑表达式，表达式长度不超过$1000000$。

数据保证，字符串中只有 x , ( , ) , | , & , ~ 以及0-9$16$个符号。

数据保证，字符串是一个合法的逻辑表达式。

合法的逻辑表达式的定义如下：

$<$表达式$>$ $=$ ( $+ <$表达式$> + <$符号$> + <$变量$> +$ )例如：x3|x4 (x2&x4|~x5)

$<$变量$> =$ ~ $+$ x $+ <$数字$>$ 例如：~x3 x4 x100

$<$数字$> =$ 1 $|$ 2 $|$ 3 $\cdots |$ 1000000; 例如： 1 3 5

符号的优先级与运算方式参见C语言标准。

Output

输出包含$1$行，包含$1$个整数，代表选择的方案数，因为这个数可能很大，所以你只用输出这个数对$1000000007$取模后的值。

Samples

(x1&x2)

1

(x1&x2)|(x3&x4)|(~(x5|x6)&(x7&x8))

121

Note

样例$1$解释：当$x1,x2$均为$1$时，表达式的值为$1$。

Resources

2014 UESTC Training for Data Structures