Hide

Problem B
Dijkstra Two Stack

Mathematical expressions can be evaluated with Dijkstra’s Two-Stack Algorithm, thus beginning to bridge the wide gap between mathematicians and programmers. However, being the programming purist that you are, you would never write an expression like “ $4 + 6^{2}$ ” when what you really mean is add(4, sqr(6)). You have decided to adapt Dijkstra’s Two-Stack algorithm to evaluate expressions like you write them!

You have the following function signatures in your repertoire:

int add(int x, int y)

Returns the sum of integers $x$ and $y$ .

Mathematicians might write it as $x + y$ .

int sqr(int x)

Returns the square of $x$ .

Mathematicians might write it as $x^{2}$ .

int min(int x, int y, int z)

Returns the smallest number of $x$ , $y$ and $z$ .

Mathematicians might write it as $min {x, y, z}$ .

In an attempt to avoid pesky overflow issues, you have decided that all functions in your repertoire return their answers modulo $1 000 000 007$ .

Input

The first and only line of the input consists of the expression you want to solve. It contains at most $100 000$ function calls. You may assume all integers in the input are non-negative. For simplicity you may also assume that there are added spaces between each of the tokens in the input (see samples).

Feel free to use the code at https://algs4.cs.princeton.edu/13stacks/Evaluate.java.html as a starting point if you want.

Output

Output a single integer, the integer value represented by the expression.

Sample Input 1	Sample Output 1
add ( 4 , sqr ( 6 ) )	40

Sample Input 2	Sample Output 2
min ( add ( 1000000000 , 7 ) , sqr ( sqr ( 2 ) ) , 1 )	0

Problem BDijkstra Two Stack

Input

Output

Problem B
Dijkstra Two Stack