在这个问题中,我们考虑四个变量 A、B、C、D 的布尔函数。变量 A、B、C 和 D 是逻辑变量,可以取值 0 或 1。我们将使用以下语法定义一个函数:
<表达式> ::= <变量> | (<表达式>) <运算符> (<表达式>)
<变量> ::= 'A' | 'B'| 'C'| 'D'| '一个' | 'b' | 'c' | 'd'
<运算符> ::= '&' | '|'
这里大字母A、B、C、D代表变量,小字母代表它们的否定。例如,如果A = 1,则字符'A'对应于值1,值字符'a'对应于值0。这里字符'&'对应于逻辑与运算,字符'|'对应于逻辑与运算。对应于逻辑OR的运算。
给定表达式 s,定义函数 f,其中缺少一些操作和变量。您还知道 n 个不同的变量值集的函数 f(A, B, C, D) 的值。计算恢复表达式中缺失元素的方法数量,以便结果表达式对应于给定变量集中函数 f 的给定信息。由于结果的值可能相当大,因此打印其模 109 + 7 的余数。
输入
第一行包含表达式 s (1 ≤ |s| ≤ 500),其中运算符和/或变量的某些字符被字符“?”替换。
第二行包含数字 n (0 ≤ n ≤ 24) — 我们知道函数 f(A, B, C, D) 值的整数集的数量。接下来的n行包含集合的描述:其中第i行包含五个整数ai,bi,ci,di,ei(0≤ai,bi,ci,di,ei≤1),用空格分隔,意味着f(ai,bi,ci,di)= ei。
保证所有元组(ai、bi、ci、di)都是不同的。
输出
在一行中打印问题的答案。
示例
输入 #1
? 2 1 0 1 0 1 0 1 1 0 1
输出 #1
2
输入 #2
(A)?(?) 1 1 1 0 0 0
输出 #2
4
输入 #3
((?)&(?))|((?)&(?)) 0
输出 #3
4096
输入#4
b 1 1 0 1 1 1
输出#4
1
注意
在第一个示例中,两个有效表达式是“C”和“d”。
在第二个示例中,表达式如下所示:“(A)&(a)”、“(A)&(b)”、“(A)&(C)”、“(A)&(D)”。