408659: GYM103256 H Truth Table

H. Truth Tabletime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Consider infix boolean expressions, consisting of:

• Single lowercase letters from the english alphabet for variable names, which can be equal to $$$0$$$ (FALSE) or $$$1$$$ (TRUE)
• Unary NOT operator: $$$\sim$$$
• Binary AND operator: &
• Binary XOR operator: ^
• Binary OR operator: |
• Binary NAND operator: #
• Binary XNOR operator: %
• Binary NOR operator: $
• Opening and closing parenthesis: ( and )
• No spaces

Now let's define the operator precedence for binary operators: let $$$p_\star$$$ be the precedence for the operator $$$\star$$$, the lower $$$p_\star$$$ is, the higher its precedence is. For example, consider the consider the expression $$$a \star_1 b \star_2 c$$$:

• If $$$p_{\star_1} < p_{\star_2}$$$, then $$$\star_1$$$ has higher precedence than $$$\star_2$$$ and is evaluated first, so the expression can be read as $$$(a \star_1 b) \star_2 c$$$.
• If $$$p_{\star_1} > p_{\star_2}$$$, then $$$\star_2$$$ has higher precedence than $$$\star_1$$$ and is evaluated first, so the expression can be read as $$$ a \star_1 (b \star_2 c)$$$.
• If $$$p_{\star_1} = p_{\star_2}$$$, then the expression will be evaluated from left to right, that is, we use left-associativity, so the expression can be read as $$$(a \star_1 b) \star_2 c$$$.

Parenthesis have the highest precedence, and unary NOT $$$\sim$$$ has the second highest precedence. The precedence of the binary operators is strictly lower than those.

Your task is to build the truth table for a given boolean expression $$$s$$$, but to reduce the size of the output, let's hash it in the following manner:

• Let $$$m$$$ be the number of distinct variables in $$$s$$$, and let $$$x_0, x_1, \ldots, x_{m-1}$$$ be the variables in increasing order with respect to their index in the alphabet.
• Let the answer be $$$0$$$.
• Build a table with $$$2^m$$$ rows numbered from $$$0$$$ to $$$2^m-1$$$.
• For every row with number $$$r$$$, assign the $$$m$$$ binary digits of $$$r$$$ to the variables: $$$x_{m-1}$$$ gets the least significant digit and so on until $$$x_0$$$ which gets the most significant digit. If $$$s$$$ evaluates to $$$1$$$ for this combination of values, add $$$2^r$$$ to the answer.
• Since the answer can be very big, only find it modulo $$$10^{18}+3$$$.

Input

The first line contains a string $$$s$$$ ($$$1 \leq |s| \leq 100$$$): an infix valid boolean expression with at most $$$16$$$ distinct variables.

The second line contains six integers, each between 2 and 7: $$$p_\&$$$, $$$p_\wedge$$$, $$$p_|$$$, $$$p_\#$$$, $$$p_\%$$$ and $$$p_\$$$$, the precedence for each binary operator.

Output

Print one integer: the hash of the truth table for the expression $$$s$$$.

ExamplesInput

x|y
2 3 4 5 6 7

Output

14

Input

~x|y&z
2 3 4 5 6 7

Output

143

Input

~x|y&z
2 3 2 5 6 7

Output

138

Input

a%b|c^(d&e#f)$g
4 2 5 3 7 6

Output

123140419684712618

Input

~~x
2 3 4 5 6 7

Output

2

Note

The truth tables for the six binary operators are: $$$$$$ \begin{array}{|c|c|c|c|c|} \hline x & y & x \& y & x \wedge y & x | y & x \# y & x \% y & x \$ y \\ \hline 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline \end{array} $$$$$$

In the second example we see that & is evaluated first than |, so the truth table is: $$$$$$ \begin{array}{|c|c|c|} \hline Row & x & y & z & \sim x | y \& z \\ \hline 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 2 & 0 & 1 & 0 & 1 \\ \hline 3 & 0 & 1 & 1 & 1 \\ \hline 4 & 1 & 0 & 0 & 0 \\ \hline 5 & 1 & 0 & 1 & 0 \\ \hline 6 & 1 & 1 & 0 & 0 \\ \hline 7 & 1 & 1 & 1 & 1 \\ \hline \end{array} $$$$$$ The rows that evaluate to $$$1$$$ are $$$0,1,2,3,7$$$, so the answer is $$$2^0+2^1+2^2+2^3+2^7=143$$$.

In the third example both & and | have the same precedence, so we evaluate from left to right (remember that $$$\sim$$$ still has higher precedence): $$$$$$ \begin{array}{|c|c|c|} \hline Row & x & y & z & \sim x | y \& z \\ \hline 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 2 & 0 & 1 & 0 & 0 \\ \hline 3 & 0 & 1 & 1 & 1 \\ \hline 4 & 1 & 0 & 0 & 0 \\ \hline 5 & 1 & 0 & 1 & 0 \\ \hline 6 & 1 & 1 & 0 & 0 \\ \hline 7 & 1 & 1 & 1 & 1 \\ \hline \end{array} $$$$$$ The rows that evaluate to $$$1$$$ are $$$1,3,7$$$, so the answer is $$$2^1+2^3+2^7=138$$$.