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

1. & 表示逻辑与运算；

2. | 表示逻辑或运算；

3. ^ 表示逻辑异或运算。

表达式还包含三种基本逻辑值：0、1、?。 每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？ 由于答案可能很大，请输出方案数模 1,000,000,007 的余数。 前缀表达式的定义如下：

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

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

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

输入格式

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

输出格式

单个整数：表示答案模 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。

限制

时间限制：1000，内存限制：512000