행렬 연쇄 곱셈

$A*B*C*D*E$ 와 같이 여러 행렬을 곱하는 식을 계산한다고 하자. 여기서 A, B, C, D, E 는 행렬이다.

행렬 곱셈은 결합법칙을 만족하므로 곱셈을 수행하는 순서는 자유롭게 정할 수 있다. 하지만 어떤 순서로 계산하느냐에 따라 필요한 원소 곱셈(elementary multiplication)의 횟수는 크게 달라진다.

예를 들어 $A$ 가 $50 \times 10$ 행렬, $B$ 가 $10 \times 20$ 행렬, $C$ 가 $20 \times 5$ 행렬이라고 하자.

$A*B*C$ 를 계산하는 방법은 $(A*B)*C$ 와 $A*(B*C)$ 두 가지가 있다.

첫 번째 방법은 원소 곱셈이 15000번 필요하지만, 두 번째 방법은 3500번만 필요하다.

괄호로 지정된 계산 순서에 따라 필요한 원소 곱셈의 횟수를 구하는 프로그램을 작성하여라.

입력은 두 부분, 즉 행렬 목록과 식 목록으로 이루어진다.

첫째 줄에는 행렬의 개수를 나타내는 정수 $n$ ($1 \le n \le 26$) 이 주어진다. 이어지는 $n$ 개의 줄에는 각각 행렬의 이름을 나타내는 대문자 하나와, 그 행렬의 행 수와 열 수를 나타내는 두 정수가 주어진다.

입력의 둘째 부분은 다음 EBNF 문법을 엄격히 따른다.

SecondPart = Line { Line } <EOF>
Line       = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"

각 줄은 하나의 식이며, 파일의 끝까지 여러 식이 이어질 수 있다.

입력의 둘째 부분에 있는 각 식에 대해 한 줄씩 출력한다. 곱셈 과정에서 두 행렬의 크기가 맞지 않아 오류가 발생하면 "error" 를 출력한다. 그렇지 않으면 괄호로 지정된 순서대로 식을 계산할 때 필요한 원소 곱셈의 횟수를 출력한다.