D. Exponentiation calculator
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Petya came across an unusual calculator. It does not have the usual "+", "-", "*" and "/" buttons. Maybe this is for the best, because the buttons for dialing numbers ("0", "1", ..., "9") and getting the result ("=") are located in their places. But what is most unusual about this calculator is the presence of "^{}" and "^{}^{}" buttons.

After many experiments with this calculator, Petya found out what these buttons mean.

The "^{}" button means the exponentiation operation $$$a^b$$$. For example, if you enter the expression "2^{}3" in the calculator, then as a result, it will display the number $$$2^3 = 8$$$.

The button "^{}^{}" means tetration $$$\displaystyle {^{b}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}} _{b}$$$. For example, if you enter the expression "2^{}^{}3", then as a result the calculator will display the number $$$^{3}2 = 2^{2^2} = 16$$$.

Petya planned to calculate several expressions on this calculator. Unfortunately, his experiments were enough to deal with the device of the calculator, but they were also enough to bring the calculator into an inoperable state.

Help Petya calculate the values of the remaining expressions. To do this, it is necessary to implement a program that processes the expression taking into account the precedence of operations. Tetration has a higher precedence (compared to exponentiation), so such operations must be performed first. It should also be borne in mind that the calculation of degrees and tetrations must be started from the farthest levels to the initial one. For example, the entry "a^{}^{}b^{}^{}c" should evaluate to $$$^{(^{c}b)}a$$$ and the expression "a^{}b^{}c" — as $$$a^{(b^c)}$$$.

Input

The single line contains an expression without spaces, consisting of positive integers, operators "^{}" (exponentiation) and operators "^{}^{}" (tetration).

The number of characters in a line does not exceed $$$100\,000$$$.

It is guaranteed that all numbers do not contain leading zeros, the expression begins and ends with a number, the expression cannot contain two consecutive operators (there are no more than two characters "^{}" in a line).

Note that there is no limit to the number of digits in a number.

Output

In a single line print the result of evaluating the expression. Since the result may be too large, output it modulo $$$10^9 + 7$$$.

Examples
Input
2^^4
Output
65536
Input
42^^1^^2^1^^3
Output
42
Input
20^^2^^2
Output
634985421
Input
1000000013000000042^1000000013000000042
Output
0
Note

In the second example, the expression looks like this:

$$$$$$ (^{(^{2}1)}42)^{(^{3}1)} $$$$$$