ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Towers of Hanoi Strike Back

Time limit: 1.0 second
Memory limit: 64 MB
The Tower of Hanoi puzzle was invented by French mathematician Édouard Lucas in the second half of the 19th century. Here is its formulation.
There are three rods, denoted by the letters A, B, and C, and n disks of different integer sizes from 1 to n. Initially the disks are stacked in ascending order of size on rod A, the smallest at the top, thus making a conical shape. Each move consists of taking the upper disk from one of the rods and placing it on top of the stack at another rod, with the following condition satisfied: no disk may be placed on top of a smaller disk. The objective of the puzzle is to move the entire stack to rod B in the smallest possible number of moves. The auxiliary rod C can be used in the process.
The state of the rods at each time can be described by a string of n letters A, B, and C: the letter at position i denotes the rod where the disk of size i is at that time. For example, the initial state is given by the string containing letters A only, and the final state is described by the string consisting of letters B. The converse is also true: any such string uniquely describes a valid state of the rods, because the order of disks on a rod is uniquely defined by their size.
Imagine that you are required to pass from the initial state, where all the disks are on rod A, to some prescribed state. What is the smallest number of moves in which this can be done?

Input

The first line contains an integer n (1 ≤ n ≤ 50).
In the second line you are given n uppercase English letters A, B, C, which describe the final state.

Output

If it is impossible to obtain the final state from the initial state, output “-1” (without quotation marks). Otherwise, output the minimum number of moves. It is guaranteed that, if there is an answer, it does not exceed 1018.

Samples

inputoutput
1
A
0
4
BBBB
15
7
BCCBABC
95
Problem Author: Nikita Sivukhin and Édouard Lucas
Problem Source: Ural Regional School Programming Contest 2014
To submit the solution for this problem go to the Problem set: 2029. Towers of Hanoi Strike Back