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 109+7.
Output
In a single line print the answer to the problem.
Note
In the first sample the two valid ex
pressions are 'C' and 'd'.
In the second sample the expressions look as follows: '(A)&(a)', '(A)&(b)', '(A)&(C)', '(A)&(D)'.