逻辑表达式

题目描述

给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值：0、1、?。

每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？

由于答案可能很大，请输出方案数模1,000,000,007 的余数。

前缀表达式的定义如下：

0、1、? 都是前缀表达式；

如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；

不满足以上两条规则的表达式都不是前缀表达式。

输入格式

单个字符串表示输入的前缀表达式

输出格式

单个整数：表示答案模 1,000,000,007 的余数。

 

输入样例#1

&??

输出样例#1

3

输入样例#2

||??|||?^?|0|1&???|??

输出样例#2

4

输入样例#3

|?^?|0|&??||?^?|1??

输出样例#3

64

说明提示

设 ∣s∣表示输入字符串的长度

50%的数据，1≤∣s∣<1,000

100%的数据，1≤∣s∣<200,000

限制

时间限制：1000ms

内存限制：512MiB