CF582E.Boolean Function

In this problem we consider Boolean functions of four variables A, B, C, D. Variables A, B, C and D are logical and can take values 0 or 1. We will define a function using the following grammar:

::= | () ()

::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

::= '&' | '|'

Here large letters A, B, C, D represent variables, and small letters represent their negations. For example, if A = 1, then character 'A' corresponds to value 1, and value character 'a' corresponds to value 0. Here character '&' corresponds to the operation of logical AND, character '|' corresponds to the operation of logical OR.

You are given expression s, defining function f, where some operations and variables are missing. Also you know the values of the function f(A, B, C, D) for some n distinct sets of variable values. Count the number of ways to restore the elements that are missing in the expression so that the resulting expression corresponded to the given information about function f in the given variable sets. As the value of the result can be rather large, print its remainder modulo 109 + 7.

本题中，我们考虑四个变量 $A$、$B$、$C$、$D$ 的布尔函数。变量 $A$、$B$、$C$、$D$ 为逻辑变量，取值为 $0$ 或 $1$。我们将使用如下文法定义一个函数：

<expression> ::= <variable> | (<expression>) <operator> (<expression>)

<variable> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd'

<operator> ::= '&' | '|'

其中大写字母 $A$、$B$、$C$、$D$ 表示对应变量，小写字母表示对应变量的否定。例如，若 $A = 1$，则字符 'A' 对应值 $1$，而字符 'a' 对应值 $0$。字符 '&' 对应逻辑与（AND）运算，字符 '|' 对应逻辑或（OR）运算。

给定一个表达式 $s$，它定义了函数 $f$，但其中部分运算符和变量缺失。此外，你还知道函数 $f(A, B, C, D)$ 在 $n$ 个不同的变量取值组合上的值。请计算将表达式中缺失部分补全的方式总数，使得所得完整表达式在给定的变量取值组合上与已知的函数值完全一致。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

The first line contains expression s (1 ≤ |s| ≤ 500), where some characters of the operators and/or variables are replaced by character '?'.

The second line contains number n (0 ≤ n ≤ 24) — the number of integers sets for which we know the value of function f(A, B, C, D). Next n lines contain the descriptions of the sets: the i-th of them contains five integers a__i, b__i, c__i, d__i, e__i (0 ≤ a__i, b__i, c__i, d__i, e__i ≤ 1), separated by spaces and meaning that f(a__i, b__i, c__i, d__i) = e__i.

It is guaranteed that all the tuples (a__i, b__i, c__i, d__i) are distinct.

第一行包含一个表达式 $s$（$1 ≤ |s| ≤ 500$），其中部分运算符和/或变量被字符 ? 替换。

第二行包含一个整数 $n$（$0 ≤ n ≤ 24$）—— 表示已知函数 $f(A, B, C, D)$ 值的整数集合个数。接下来的 $n$ 行描述这些集合：第 $i$ 行包含五个整数 $a_i, b_i, c_i, d_i, e_i$（$0 ≤ a_i, b_i, c_i, d_i, e_i ≤ 1$），以空格分隔，表示 $f(a_i, b_i, c_i, d_i) = e_i$。

保证所有元组 $(a_i, b_i, c_i, d_i)$ 互不相同。

In a single line print the answer to the problem.

在一行中输出问题的答案。

In the first sample the two valid expressions are 'C' and 'd'.

In the second sample the expressions look as follows: '(A)&(a)', '(A)&(b)', '(A)&(C)', '(A)&(D)'.

在第一个样例中，两个合法的表达式是 'C' 和 'd'。

在第二个样例中，表达式如下：'(A)&(a)'、'(A)&(b)'、'(A)&(C)'、'(A)&(D)'。