题目描述

Y 同学研究四个布尔变量 $A,B,C,D$ 构成的表达式。大写字母表示变量本身，小写字母 $a,b,c,d$ 分别表示对应变量取反；二元运算符 & 表示与，| 表示或。合法表达式要么是一个文字，要么形如 (<表达式>)<运算符>(<表达式>)。

现在表达式中的若干文字或运算符被替换成了 ?。若 ? 位于文字位置，可以填入 A,B,C,D,a,b,c,d 中任意一个；若位于运算符位置，可以填入 & 或 |。此外，Y 同学给出了若干组不同的变量取值及表达式应输出的值。

请你计算有多少种填法能同时满足所有已知取值，答案对 $10^9+7$ 取模。

输入格式

第一行包含表达式字符串 $s$。

第二行包含整数 $n$。

接下来 $n$ 行，每行五个整数 $A_i,B_i,C_i,D_i,E_i$，表示该组取值下表达式结果应为 $E_i$。

输出格式

输出一行一个整数，表示合法填法数对 $10^9+7$ 取模后的结果。

样例

样例输入 #1

?
1
1 0 1 0 1

样例输出 #1

4

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le |s|\le500$，$0\le n\le16$，给出的 $(A_i,B_i,C_i,D_i)$ 互不相同。

特殊性质 A：保证没有运算符问号。 特殊性质 B：保证 $n=0$。