Engineering Calculator

Hyeonseok is solving chemistry problems to prepare for his final exam. While working on them, he remembers that he left his engineering calculator in his homeroom locker. Too lazy to go all the way down to the locker, he decides to just write code and make a calculator.

Hyeonseok's calculator supports the operators +, -, *, /, ^, (, ), and #. They mean addition, subtraction, multiplication, division, exponentiation, opening and closing parentheses, and square root, respectively. The square root operator is placed in front of the expression whose square root is wanted, as in #5 or #(1+2). To evaluate an expression, you must enter the whole expression and then press the = button. The inputs the calculator can handle are stated precisely by the following grammar.

<input>    ::= <expr> "="
<expr>     ::= <term> | <term> ("+" | "-") <expr>
<term>     ::= <factor> | <factor> ("*" | "/") <term>
<factor>   ::= <power> | <power> "^" <factor>
<power>    ::= "#" <power> | <root>
<root>     ::= <num> | "(" <expr> ")"
<num>      ::= "0" | <non-zero> <digit>*
<digit>    ::= "0" | <non-zero>
<non-zero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Operator precedence is parentheses > square root > exponentiation > multiplication and division > addition and subtraction. When several operators of the same precedence appear, all except square root and exponentiation are evaluated from left to right, while square root and exponentiation are evaluated from right to left. That is, 2^3^2 is evaluated as 2^(3^2), and ##32 is evaluated as #(#32).

Hyeonseok's calculator can only do integer arithmetic. If the result of a square root or a division is not an exact integer, it takes the nearest integer toward 0 as the result instead. For example, the result of #17 is 4, and the result of (2-9)/3 is -2.

After coding for a while, Hyeonseok thinks it would be faster to just calculate by hand. Let's make a calculator for Hyeonseok, who cannot code!

An expression to evaluate is given. Its length does not exceed 100, and it satisfies the grammar given in the problem. The input is also guaranteed to satisfy the following conditions.

• Every number that appears during evaluation can be represented as a signed 64-bit integer.
• No operation during evaluation takes the square root of a negative number or raises a number to a negative power.
• No operation during evaluation raises 0 to the power 0 or divides a number by 0.

Print the result of the evaluation.