H. Truth Table
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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} \lt 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} \gt 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$$$.

Examples
Input
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$$$.