cho.sh

Fygon 2.0

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.

Medium7MathCombinatoricsImplementationSimulationNo attempts yetTime limit3sMemory limit512 MB

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)f(n) be the number of lag operations the program executes, as a function of nn. For a non-negative integer kk and a positive rational number CC, we call C⋅nkC \cdot n^k the asymptotic complexity of the program if

lim⁡n→∞f(n)C⋅nk=1\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 mm, the number of lines of the Fygon 2.0 program. The next mm 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≤m≤212 \le m \le 21.

Output

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