Problem Description

The Hanoi Tower consists of three poles (denoted as A, B, and C) and n disks of different sizes. Initially, all n disks are stacked on pole A, with the largest at the bottom and the smallest at the top, forming a conical tower. A legal move in the Hanoi Tower involves taking the top disk from one pole and placing it on top of another pole, ensuring that the moved disk is placed above a larger disk (or on an empty pole without this requirement). We can describe a move using two letters: the first letter represents the starting pole, and the second letter represents the target pole. For example, AB means moving the top disk from pole A to pole B. The goal of the Hanoi Tower game is to move all disks from pole A to either pole B or pole C.

There is a simple and classic strategy to complete the game. Before any move, we assign arbitrary priorities to the six possible moves (AB, AC, BA, BC, CA, and CB) in any order. Then, we always choose a move that satisfies the following two conditions until all disks are moved from pole A to another pole:
1. This move has the highest priority among all legal moves.
2. The disk being moved is not the same disk that was moved in the last operation.

It can be proven that this strategy will always complete the Hanoi Tower game. Your task is to calculate the number of steps required to move the disks according to the given priorities and the described strategy.

Input Format

The input consists of two lines. The first line contains an integer n (1 ≤ n ≤ 30), representing the number of disks. The second line is a string of uppercase ABC characters, representing the priorities of the six moves, with higher priority moves listed first. Each move is separated by a space.

Output Format

Output a single number, which represents the number of moves required. We guarantee that the answer will not exceed 10^18.

Sample Input and Output

Sample Input #1

3
AB BC CA BA CB AC

Sample Output #1

7

Sample Input #2

2
AB BA CA BC CB AC

Sample Output #2

5

Notes

For 20% of the data, n ≤ 10.
For 100% of the data, n ≤ 30.

见题面 Input 部分

见题面 Output 部分