Известная задача о Ханойских башнях была придумана французским математиком Эдуардом Люка во второй половине XIX века. Она звучит так:

Есть три стержня, обозначенных буквами A, B, C, и n дисков размеров от 1 до n (все целые и различные). Изначально все диски нанизаны на стержень A, причём чем больше размер диска, тем он ниже. Можно снимать верхний диск с любого стержня и перекладывать его на другой стержень, но всегда должно выполняться следующее условие: для любых двух дисков на одном стержне выше тот, который меньше по размеру. Нужно переместить все диски на стержень B за наименьшее число ходов, причём в процессе можно использовать вспомогательный стержень C.

Состояние стержней в любой момент времени можно описывать строчкой из n букв A, B, C: на позиции номер i стоит буква, обозначающая стержень, на который в данный момент нанизан диск размера i. Например, начальное состояние задаётся строчкой из всех букв А, а конечное — строчкой из всех букв В. Верно и обратное: любая такая строчка задаёт ровно одно корректное состояние стержней, т.к. порядок дисков на стержне однозначно определяется их размером.

Представьте, что вам нужно перейти из начального состояния, в котором все диски нанизаны на стержень A, в некоторое заданное состояние. За какое минимальное количество ходов это можно сделать?

В первой строке дано целое число n (1 ≤ n ≤ 50).

Во второй строке даны n заглавных латинских букв A, B, C, описывающих конечное состояние.

Если не существует способа получить из начального состояния конечное, выведите «-1» (без кавычек). Иначе выведите единственное число — минимальное количество ходов. Гарантируется, что если ответ существует, то он не превышает 10¹⁸.