该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个以后缀形式表示的逻辑表达式，包含：

运算符：&（与）、|（或）、^（异或）

操作数：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

数据规模与约定

$1 \le |s| < 200,000$