B. Красные и синие шарики
ограничение по времени на тест
0.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У пользователя ainta есть стек, в котором содержатся n красных и синих шариков. Он умеет выполнять со стеком операцию, которая изменяет цвета шаров в стеке. Операция описывается алгоритмом:

  • Пока на вершине стека лежит красный шар, изъять шар из вершины стека.
  • Затем заменить синий шар, который сейчас находится на вершине стека, на красный.
  • Наконец, добавлять в стек синие шарики до тех пор, пока в стеке не будет n шариков.
 

Если в стеке нет синих шариков, ainta не сможет выполнить описанную операцию. По заданному изначальному состоянию стека, ainta хочет узнать, какое наибольшее количество операций он может выполнить одну за другой. Помогите ему, посчитайте это значение.

Входные данные

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

Во второй строке записана последовательность s (|s| = n), описывающая изначальное состояние стека: i-й символ в строке s обозначает цвет i-го шарика (считайте, что шарики в стеке пронумерованы, начиная от вершины стека). Если символ равняется "R", то шарик красный. Если символ равняется "B", то шарик синий.

Выходные данные

Выведите максимальное количество операций, которые ainta может последовательно выполнить.

Пожалуйста, не используйте спецификатор %lld для чтения и записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
RBR
Выходные данные
2
Входные данные
4
RBBR
Выходные данные
6
Входные данные
5
RBBRR
Выходные данные
6
Примечание

Описание первого тестового примера.

Вот как пользователь ainta выполняет первую операцию. Он вытаскивает один красный шарик, меняет шарик в центре с синего на красный и добавляет в стек один синий шарик.

Вот как пользователь ainta выполняет вторую операцию. Так как на вершине стека синий шар, он не будет вытаскивать красные шары. Он просто меняет верхний шар с синего на красный.

Теперь ainta больше не может применить ни одной операции, поскольку в стеке не осталось синих шаров. ainta выполнил две операции, так что ответ равняется 2.

Описание второго примера приведено ниже. Синяя стрелка обозначает применение одной операции.