CF582E Boolean Function

在本题中，我们考虑四个变量 $A,B,C,D$ 的布尔函数。变量 $A,B,C,D$ 是逻辑值，可以取值 $0$ 或 $1$。我们将使用以下语法来定义一个函数： ::= | () () ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd' ::= '&' | '|' 其中，大写字母 $A,B,C,D$ 代表变量本身，小写字母分别表示其取反。例如，如果 $A=1$，则字符 'A' 对应值 $1$，字符 'a' 对应值 $0$。运算符 '&' 表示逻辑与，'|' 表示逻辑或。 现在，给定一个表达式 $s$，用来定义函数 $f$，其中部分操作符和变量被替换成了字符 '?'。你还知道 $f(A,B,C,D)$ 对于某 $n$ 个不同变量取值的结果。请你计算，有多少种方式可以填补表达式中缺失的部分，使得完整的表达式在给定的变量取值下，输出期望的 $f$ 值。由于答案可能很大，请输出答案对 $10^9+7$ 取模的结果。

第一行给出表达式 $s$（$1 \leq |s| \leq 500$），其中部分操作符和/或变量被替换成了字符 '?'。 第二行包含一个整数 $n$（$0 \leq n \leq 2^{4}$），表示已知的变量组合下函数 $f(A,B,C,D)$ 的值的数量。接下来的 $n$ 行，每行包含五个整数 $a_i, b_i, c_i, d_i, e_i$（$0 \leq a_i, b_i, c_i, d_i, e_i \leq 1$），表示 $f(a_i, b_i, c_i, d_i) = e_i$。 保证所有的元组 $(a_i, b_i, c_i, d_i)$ 均不重复。

输出一个整数，表示满足条件的合法表达式的总数，结果对 $10^9+7$ 取模。

在第一个样例中，合法的表达式为 'C' 和 'd'。 在第二个样例中，合法表达式可以为 '(A)&(a)'、'(A)&(b)'、'(A)&(C)'、'(A)&(D)'。 由 ChatGPT 5 翻译