Fygon#7617

Fygon

1 second

128 megabytes

Very hard

Frederick is a young programmer. He takes part in every programming contest he can find and always uses his favorite programming language, Fygon. Unfortunately, he often gets the Time Limit Exceeded verdict, even when his algorithm is asymptotically optimal. This happens because the Fygon interpreter is very slow. Nevertheless, Frederick likes Fygon so much that he resorts to non-asymptotic optimizations to fit his solutions into the time limit. To make this easier, he asks you to write a program that computes the exact number of operations his Fygon program performs.

For simplicity, we assume that Fygon has only two kinds of statements. The first one is lag, which can stand in for almost any other statement. The second one is the for loop:

for <variable> in range (<limit>):
    <body>

Here <variable> takes all values from $0$ to <limit> - $1$ . In Fygon, <variable> is a lowercase letter from $a$ to $z$ , and <limit> is either a previously defined <variable> or a positive integer constant. The <body> of the loop is indented by four spaces and contains at least one statement.

The program receives its input in the variable $n$ . This variable has a special meaning and cannot be used as a loop variable.

Your task is to find a formula that gives the number of lag operations performed by the given Fygon program as a function of $n$ .

Input

Contains a Fygon program. No two loops use the same variable as their iterator. Every variable used inside range is either $n$ or a variable declared in one of the enclosing loops.

The program contains at most $20$ statements, and at most $6$ of them are loops. All integer constants are between $1$ and $9$ , inclusive.

Output

Print a formula for the number of lag operations performed, as a function of $n$ . The formula must be at most $100$ characters long (not counting spaces) and must conform to the following grammar:

<Expression> ::= <Product> (('+' | '-') <Product>)*
<Product>    ::= <Value> ('*' <Value>)*
<Value>      ::= 'n' | <Number> | '-' <Value> | '(' <Expression> ')'
<Number>     ::= ['0'..'9']+ ('/' ['0'..'9']+)?

Examples

Example 1