Fygon 2.0

Time limit3sMemory limit512 MB

Summary

Given nested Fygon loops with inclusive ranges over variables and n, compute the asymptotic complexity C*n^k of the single lag execution count, with C as an irreducible fraction.

Level: Medium7 of 10
Topics: Math, Combinatorics, Implementation, Simulation
Solved: No attempts yet

Problem

A new version of the programming language Fygon is out. Fygon 2.0 still has only two statements.

The first statement is lag. It replaces almost any other statement. The second statement is a for loop.

for <variable> in range(<from>, <to>):
    <body>

The loop moves <variable> from <from> to <to>, both inclusive.
If <from> is greater than <to>, <body> does not run at all.
<variable> is a lowercase letter from a to z, except n, which is a variable defined before the given code fragment.
<from> and <to> can be any variable defined in an outer loop. On top of that, <from> can be 1 and <to> can be n.
The <body> of the loop is indented by four spaces and contains at least one statement.

If you know Fygon 1.0, note that Fygon 2.0 is not backwards compatible, because the range function now takes two parameters.

The new version runs much faster, so programs can nest for loops more deeply. For that reason the exact number of operations no longer matters, only the asymptotic complexity of the program. In every program given to you, all for loops are nested in a single chain, and exactly one lag statement sits inside all of them. All loop variables are distinct, and none of them is n.

Let $f(n)$ be the number of lag operations the program executes, as a function of $n$ . For a non-negative integer $k$ and a positive rational number $C$ , we call $C \cdot n^k$ the asymptotic complexity of the program if

$\lim_{n \to \infty} \frac{f(n)}{C \cdot n^k} = 1$

Given a Fygon 2.0 program, find its asymptotic complexity.

Input

The first line contains one integer $m$ , the number of lines of the Fygon 2.0 program. The next $m$ lines contain the program itself.

The program has at least 1 and at most 20 for statements, and every for statement contains either one nested for statement or the lag statement, so $2 \le m \le 21$ .

Output

Print $k$ and $C$ on one line, separated by a single space. Print $C$ as an irreducible fraction p/q, where $p$ and $q$ are coprime positive integers. Print the denominator even when it equals 1, so write 1/1 and not 1.

Examples2

Example 1

Input

4
for i in range(1, n):
    for j in range(1, i):
        for k in range(j, n):
            lag

Expected output

3 1/3

Example 2
Input
```
2
for i in range(1, n):
    lag
```
Expected output
```
1 1/1
```