변형 하노이

세 개의 폴 A, B, C와 크기가 모두 다른 디스크 N개가 있다. 처음에는 모든 디스크가 A 폴에 작은 디스크가 위에 오도록 쌓여 있다.

한 번의 이동에서는 어떤 폴의 가장 위에 있는 디스크 하나를 다른 폴로 옮긴다. 단, 큰 디스크를 작은 디스크 위에 올릴 수 없다.

이 문제에서는 일반적인 하노이 규칙에 다음 두 조건이 추가된다.

• 같은 디스크를 연속해서 두 번 옮길 수 없다.
• 가능한 이동은 AB, AC, BA, BC, CA, CB 여섯 가지이며, 이 여섯 이동의 우선순위가 주어진다. 현재 조건을 만족하는 이동이 두 가지 이상이면, 그중 우선순위가 가장 높은 이동을 반드시 선택한다.

이 규칙대로 이동을 반복하면 모든 디스크가 B 폴 또는 C 폴 중 하나에 모이게 된다고 보장된다. 모든 디스크가 처음으로 한 폴에 모일 때까지의 이동 횟수를 구하라.

첫째 줄에 디스크의 수 N이 주어진다. (1 <= N <= 30)

둘째 줄에 여섯 가지 이동 AB, AC, BA, BC, CA, CB가 우선순위가 높은 순서대로 주어진다.

첫째 줄에 이동 횟수를 출력한다.

정답은 10^18보다 작다고 가정한다.

디스크가 2개이고 우선순위가 AB, BA, CA, BC, CB, AC인 경우에는 1번 디스크를 A에서 B로, 2번 디스크를 A에서 C로, 1번 디스크를 B에서 A로, 2번 디스크를 C에서 B로, 1번 디스크를 A에서 B로 옮기면 모든 디스크가 B 폴에 모인다.