Fygon 2.0

프로그래밍 언어 Fygon의 새 버전이 나왔다. Fygon 2.0에도 명령문은 두 가지뿐이다.

첫 번째 명령문은 lag이다. 거의 모든 다른 명령문을 대신한다. 두 번째 명령문은 for 반복문이다.

for <변수> in range(<시작>, <끝>):
    <본문>

• 반복문은 <변수>를 <시작>부터 <끝>까지 양 끝을 포함해서 움직인다.
• <시작>이 <끝>보다 크면 <본문>은 한 번도 실행되지 않는다.
• <변수>는 a부터 z까지의 소문자 하나이며 n은 쓸 수 없다. n은 주어진 코드 조각보다 앞에서 정의된 변수다.
• <시작>과 <끝>에는 바깥쪽 반복문에서 정의된 변수를 아무거나 쓸 수 있다. 그 외에 <시작>에는 1을, <끝>에는 n을 쓸 수 있다.
• 반복문의 <본문>은 공백 네 칸으로 들여쓰고, 명령문이 적어도 하나 들어 있다.

Fygon 1.0을 안다면, range 함수가 이제 매개변수를 두 개 받기 때문에 Fygon 2.0이 하위 호환되지 않는다는 점을 알아 두자.

새 버전은 훨씬 빨라져서 for 반복문을 더 깊이 중첩할 수 있다. 그래서 연산 횟수를 정확히 세는 대신 프로그램의 점근 복잡도를 구한다. 주어지는 프로그램에서 모든 for 반복문은 한 줄기로 중첩되어 있고, 모든 반복문의 가장 안쪽에 lag 명령문이 정확히 하나 있다. 반복 변수는 서로 모두 다르고 n과도 다르다.

프로그램이 실행하는 lag 연산의 횟수를 $n$에 대한 함수 $f(n)$이라고 하자. 음이 아닌 정수 $k$와 양의 유리수 $C$에 대해 다음이 성립하면 $C \cdot n^k$를 이 프로그램의 점근 복잡도라고 부른다.

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

Fygon 2.0 프로그램이 주어질 때 점근 복잡도를 구하시오.

첫째 줄에 Fygon 2.0 프로그램의 줄 수 $m$이 주어진다. 다음 $m$개 줄에 프로그램이 주어진다.

프로그램에는 for 명령문이 1개 이상 20개 이하 있고, 각 for 명령문 안에는 중첩된 for 명령문 하나 또는 lag 명령문 하나가 들어 있다. 따라서 $2 \le m \le 21$이다.

$k$와 $C$를 한 줄에 공백 하나로 구분해 출력한다. $C$는 기약분수 p/q 꼴로 출력하며, $p$와 $q$는 서로소인 양의 정수다. 분모가 1일 때도 생략하지 않고 1이 아니라 1/1로 출력한다.