CF582E.Boolean Function

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

In this problem we consider Boolean functions of four variables A,B,C,DA,B,C,D . Variables A,B,CA,B,C and DD 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,DA,B,C,D represent variables, and small letters represent their negations. For example, if A=1A=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 ss , defining function ff , where some operations and variables are missing. Also you know the values of the function f(A,B,C,D)f(A,B,C,D) for some nn 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 ff in the given variable sets. As the value of the result can be rather large, print its remainder modulo 109+710^{9}+7 .

输入格式

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

The second line contains number nn ( 0<=n<=240<=n<=2^{4} ) — the number of integers sets for which we know the value of function f(A,B,C,D)f(A,B,C,D) . Next nn lines contain the descriptions of the sets: the ii -th of them contains five integers ai,bi,ci,di,eia_{i},b_{i},c_{i},d_{i},e_{i} ( 0<=ai,bi,ci,di,ei<=10<=a_{i},b_{i},c_{i},d_{i},e_{i}<=1 ), separated by spaces and meaning that f(ai,bi,ci,di)=eif(a_{i},b_{i},c_{i},d_{i})=e_{i} .

It is guaranteed that all the tuples ( ai,bi,ci,dia_{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)'.

首页