Modified Hanoi

There are three poles A, B, and C, and N disks of distinct sizes. Initially, all disks are stacked on pole A with smaller disks above larger disks.

In one move, choose the top disk of a pole and move it to another pole. A larger disk may not be placed on top of a smaller disk.

This problem adds the following two rules to the usual Hanoi rules.

• The same disk cannot be moved twice in a row.
• The six possible directed moves are AB, AC, BA, BC, CA, and CB, and their priority order is given. If two or more moves currently satisfy all conditions, you must choose the one with the highest priority.

It is guaranteed that if you keep moving disks by these rules, eventually all disks gather on either pole B or pole C. Find the number of moves made until all disks first gather on one pole.

The first line contains the number of disks N. (1 <= N <= 30)

The second line contains the six moves AB, AC, BA, BC, CA, and CB in decreasing priority order.

Print the number of moves on the first line.

You may assume that the answer is less than 10^18.

When there are 2 disks and the priority order is AB, BA, CA, BC, CB, AC, move disk 1 from A to B, disk 2 from A to C, disk 1 from B to A, disk 2 from C to B, and disk 1 from A to B. Then all disks are gathered on pole B.