密码锁 (expression.cpp/in/out)

时间限制: 1 s / 内存限制: 512 MB / 打开O2优化

题目描述

dyx在家里玩耍时发现了一个神奇的密码锁。然而他早已忘记了这个锁的密码，于是他随便尝试了一下，结果锁就打开了......
锁的内部有一个很长的字符串，机智的dyx马上就发现这就是密码锁的核心。于是他研究了一下午，探寻这把锁的奥秘。
他发现这个字符串是一个表达式的形式，像下面这个样子：

1

a|b&(!c^d)

其中，每一个由小写字母组成的单词是一个变量，对应着密码锁上的一个按钮。由于按钮只能按下或不按下，于是你可以认为每个变量是一个布尔类型的（即只有$\text{true}$和$\text{false}$之分）
其余的字符就只有&、|、^、!和左右小括号。dyx发现括号是用来优先运算的，意思是这是一个会将所有变量进行计算的表达式，并且优先计算括号中的子表达式。同时，&、|、^、!都是运算符，它们分别对应的是逻辑与、逻辑或、逻辑异或和逻辑非。其中前三者运算优先级一致，当它们在同一级出现时会从左至右运算，逻辑非的优先级比它们高。当每一个变量都有相应的值时，整个表达式就会就会进行计算，并给出一个布尔值。dyx还发现，当整个表达式的值为$\text{true}$时，密码锁就会打开。
很明显，整个密码锁的输入方案共有$2^n$种，其中$n$是表达式中变量的数量。于是dyx瞬间明白为什么他一次就可以将这个密码锁解开了。然而dyx是一个勇于探究的人，他想知道到底有多少中方法可以解开一个密码锁。
不知为何，dyx又发现了一火车的密码锁。坚持不懈的dyx不停的计算着每一个密码锁能解开的方案数......由于密码锁的表达式越来越长并且人脑计算量是$\Theta(1)$的，dyx不得不需要一个程序来帮助他计算这个方案数。

输入格式

每个测试数据点有多个表达式。文件以EOF结束。
每一个表达式占一行，且中间只有小写字母和&、|、^、!、(、)。
对于&、|和^运算，它们左右会各有一个变量或子表达式。其运算规则如下：

对于!运算，它后面会有一个变量或子表达式。其运算规则如下：

输入保证表达式是有效的，且表达式中不存在缺少参数的运算符和空的括号。
为了防止此题变成不可做的NP-hard问题，输入保证表达式中每一个变量名只出现一次。

输出格式

对于每一个表达式，输出能够解开它的方案总数。由于答案可能过大，因此将答案对$10^9 + 7$取模后输出。
一种方案即指对每一个变量给定一个值。
两种方案不同当且仅当至少一个变量所给定的值不同。

输入样例

1
2
3

a&b
a|b|c
a|!(b|c)

输出样例

1
2
3

1
7
5

数据范围及提示

对于第一个表达式，只有$a = \text{true}, b = \text{true}$才为$\text{true}$。
对于第二个表达式，只要三者有一个变量为$\text{true}$就是$\text{true}$。
对于第三个表达式，先运算b|c，然后对其取反，最后与$a$做逻辑与。

以下$n$表示变量数量，$T$表示测试数据组数，$L$表示表达式的总长度。
对于$10\%$的数据，$n \le 10,\; T = 15$。
对于另外$10\%$的数据，只有逻辑或运算，没有括号。
对于另外$10\%$的数据，不存在逻辑非和括号。
对于另外$20\%$的数据，不存在括号。
对于另外$20\%$的数据，$n \le 500$。
对于$100\%$的数据，变量名长度$\le 4$，$L \le 10^6$，$n \le 3\times10^5$。
其中$90\%$的数据，$T \le 5$。