← 返回题目列表

Codeforces · 582/E

E. 布尔函数

中文机器翻译题面 查看原题

在这个问题中,我们考虑四个变量 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)”。