Boolean Function

题意翻译

$A,B,C,D,a,b,c,d$ 为八个布尔「变量」，其中小写字母的值等于对应大写字母的值取反。 $&,|$ 为两个布尔「操作符」。 布尔「表达式」为一个「变量」，或通过「操作符」连接起来的两个「表达式」。 布尔「函数」$f(A,B,C,D)$ 为一个布尔「表达式」。 给定一个可能缺少某些「变量」和「操作符」（用 `?` 代替）的「函数」$s$，并给出 $n$ 个**函数在 $A,B,C,D$ 确定时**的值。 求可能的「函数」个数。 $|s|\le 500$，$n \le 16$，答案对 $10^9+7$ 取模。

题目描述

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: <expression> ::= <variable> | (<expression>) <operator> (<expression>) <variable> ::= 'A' | 'B' | 'C' | 'D' | 'a' | 'b' | 'c' | 'd' <operator> ::= '&' | '|' 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 $ 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<=2^{4} $ ) — 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.

输出格式

In a single line print the answer to the problem.

输入输出样例

输入样例 #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

说明

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)'.

题意翻译

$A,B,C,D,a,b,c,d$ 为八个布尔「变量」，其中小写字母的值等于对应大写字母的值取反。 $&,|$ 为两个布尔「操作符」。 布尔「表达式」为一个「变量」，或通过「操作符」连接起来的两个「表达式」。 布尔「函数」$f(A,B,C,D)$ 为一个布尔「表达式」。 给定一个可能缺少某些「变量」和「操作符」（用 `?` 代替）的「函数」$s$，并给出 $n$ 个**函数在 $A,B,C,D$ 确定时**的值。 求可能的「函数」个数。 $|s|\le 500$，$n \le 16$，答案对 $10^9+7$ 取模。