密码锁
riteme.site

密码锁 (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结束。
每一个表达式占一行,且中间只有小写字母和&|^!()
对于&|^运算,它们左右会各有一个变量或子表达式。其运算规则如下:

$a$ $b$ $a$ & $b$ ($a \land b$)
$\text{true}$ $\text{true}$ $\text{true}$
$\text{true}$ $\text{false}$ $\text{false}$
$\text{false}$ $\text{true}$ $\text{false}$
$\text{false}$ $\text{false}$ $\text{false}$
$a$ $b$ $a$ | $b$ ($a \lor b$)
$\text{true}$ $\text{true}$ $\text{true}$
$\text{true}$ $\text{false}$ $\text{true}$
$\text{false}$ $\text{true}$ $\text{true}$
$\text{false}$ $\text{false}$ $\text{false}$
$a$ $b$ $a$ ^ $b$ ($a \oplus b$)
$\text{true}$ $\text{true}$ $\text{fasle}$
$\text{true}$ $\text{false}$ $\text{true}$
$\text{false}$ $\text{true}$ $\text{true}$
$\text{false}$ $\text{false}$ $\text{false}$

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

$a$ !$a$ ($\lnot a$)
$\text{true}$ $\text{false}$
$\text{false}$ $\text{true}$

输入保证表达式是有效的,且表达式中不存在缺少参数的运算符和空的括号。
为了防止此题变成不可做的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$