Fygon

프레데릭은 대회에 나갈 때마다 가장 좋아하는 언어 Fygon으로 문제를 푼다. Fygon 인터프리터가 느린 탓에 점근적으로 최적인 알고리즘을 짜도 시간 초과를 받는 일이 잦고, 그래서 상수 배 최적화로 시간 제한을 맞춘다. 어떤 최적화가 값어치를 하는지 판단하려면 프로그램이 수행하는 연산 횟수를 정확히 알아야 한다.

Fygon에는 문장이 두 종류뿐이다. 첫 번째는 lag으로, 다른 거의 모든 문장을 대신한다. 두 번째는 for 반복문이다.

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

반복 변수는 0부터 시작해 <limit>보다 작은 정수를 차례로 훑는다. 변수는 a부터 z까지의 소문자이고, <limit>은 이미 정의된 변수이거나 양의 정수 상수다. 반복문의 <body>는 공백 네 칸으로 들여쓰고 문장이 하나 이상 들어 있다.

프로그램은 입력을 변수 n으로 받는다. n은 특별한 의미가 있어 반복 변수로 쓸 수 없다.

Fygon 프로그램이 주어지면 이 프로그램이 실행하는 lag 연산의 횟수를 n에 대한 식으로 구하라.

입력은 Fygon 프로그램 전체다. 서로 다른 두 반복문은 같은 반복 변수를 쓰지 않는다. range 안에 나오는 변수는 n이거나 바깥쪽 반복문이 선언한 변수다. 프로그램의 문장은 20개 이하이고 그중 반복문은 6개 이하다. 정수 상수는 모두 1 이상 9 이하다. 중첩 한 단계마다 공백 네 칸을 들여쓰며, 각 줄은 lag이거나 for <variable> in range(<limit>): 형태다.

lag 연산의 횟수를 $f(n)$이라 하자. $f$는 $n$에 대한 유리계수 다항식이다. 이를 전개한 $f(n) = c_d n^d + c_{d-1} n^{d-1} + \dots + c_0$ 꼴로 보고, 아래 규칙에 따라 한 줄에 공백 없이 출력한다.

계수가 0이 아닌 항만 지수가 큰 것부터 차례로 적는다. 지수가 $k$이고 계수가 $c$인 항은 $|c|$를 적은 다음 *n을 $k$번 이어 붙인다. $|c|$는 분모가 양수인 기약분수 p/q로 적되, 분모가 1이면 p만 적는다. 계수가 1이어도 생략하지 않는다. 첫 항은 계수가 음수일 때만 앞에 -를 붙이고, 두 번째 항부터는 계수가 양수면 +를, 음수면 -를 붙인다. $f$가 항상 0이면 0 하나만 출력한다.

예를 들어 $f(n) = \frac{11}{2}n^2 - \frac{1}{2}n + 5$이면 11/2*n*n-1/2*n+5를 출력하고, lag이 한 번도 실행되지 않는 프로그램이면 0을 출력한다.