변형 하노이 탑

세 개의 기둥 A, B, C가 있다. N개의 원반을 기둥 A에서 기둥 B 또는 C 중 한 곳으로 모두 옮기려고 한다.

원반 이동 조건은 다음과 같다.

• 같은 원반을 연속으로 두 번 옮길 수 없다.
• 이동 가능한 경우가 여러 개면, 입력으로 주어진 우선순위가 가장 높은 이동을 선택한다.
• 한 번의 이동에서는 한 기둥의 가장 위에 있는 원반 하나를 다른 기둥의 가장 위로 옮긴다.
• 큰 원반 위에 작은 원반이 올 수 있지만, 작은 원반 위에 큰 원반을 올려놓을 수 없다.

위 조건에 따라 모든 원반을 옮길 때까지의 이동 횟수를 구하라.

입력

첫째 줄에 원반의 수 N이 주어진다. (1 ≤ N ≤ 30)
둘째 줄에 6개의 이동 방향이 우선순위가 높은 순서대로 공백으로 구분되어 주어진다. (예: AB BA CA BC CB AC)
각 이동 방향은 두 개의 알파벳 대문자로 구성되며, 첫 번째 문자는 출발 기둥, 두 번째 문자는 도착 기둥을 의미한다. 입력은 항상 올바른 이동 방향 6가지의 순열로만 주어진다.

출력

모든 원반을 옮기는 데 필요한 총 이동 횟수를 출력한다.

입출력 예시

입력 1

2
AB BA CA BC CB AC

출력 1

5