Description

The Towers of Hanoi consists of three pegs (denoted A, B, C) and $n$ disks of distinct sizes. Initially, all $n$ disks are stacked on peg A, with larger disks below smaller ones, forming a conical tower.

A legal move is: take the top disk from one peg and place it on top of another peg, with the constraint that the moved disk must be placed on a larger disk (this constraint is waived if the target peg is empty). We can describe a move with two letters: the first letter is the source peg, and the second is the destination peg. For example, AB means moving the top disk from peg A to peg B. The goal of the game is to move all disks from peg A onto either peg B or peg C.

There is a concise and classic strategy to complete this game. Before any move, assign distinct priorities, in any order, to the six possible moves: AB, AC, BA, BC, CA, CB. Then, repeatedly choose the move that satisfies both conditions below, until all disks have been moved from peg A to another peg: (1) Among all legal moves, it has the highest priority. (2) The disk to be moved is not the same disk that was moved in the previous step.

It can be proven that this strategy will always complete the Towers of Hanoi. Your task is: given the priority of each move, compute the number of steps needed under the strategy above.

Description

Input Format

The input consists of two lines.

• The first line contains an integer $n$ ($1 \le n \le 30$), the number of disks.
• The second line contains the six moves as a permutation of AB, AC, BA, BC, CA, CB, separated by spaces, where earlier moves have higher priority.

Output Format

Output a single integer: the number of moves. It is guaranteed that the answer does not exceed $10^{18}$.

3
AB BC CA BA CB AC

7

2
AB BA CA BC CB AC

5

Hint

• For 20% of the testdata, $n \le 10$.
• For 100% of the testdata, $n \le 30$.

Translated by ChatGPT 5