题目描述

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

• & 表示逻辑与运算
• | 表示逻辑或运算
• ^ 表示逻辑异或运算

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

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

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

后缀表达式的定义如下：

• 0、1、? 都是后缀表达式；
• 如果 x，y 都是后缀表达式，则 xy&、xy|、xy^ 都是后缀表达式；
• 不满足以上两条规则的表达式都不是后缀表达式。

输入格式

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

输出格式

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

??&

3

??|??01??&||^|?|??|||

4

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

64

数据范围

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

• $50\%$的数据，$1\leq |s|< 1,000$
• $100\%$的数据，$1\leq |s|< 200,000$