User ainta has a stack of n red and blue balls. He can apply a certain operation which changes the colors of the balls inside the stack.

  While the top ball inside the stack is red, pop the ball from the top of the stack.  Then replace the blue ball on the top with a red ball.  And finally push some blue balls to the stack until the stack has total of n balls inside.   

If there are no blue balls inside the stack, ainta can't apply this operation. Given the initial state of the stack, ainta wants to know the maximum number of operations he can repeatedly apply.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 50) — the number of balls inside the stack.

The second line contains a string s (|s| = n) describing the initial state of the stack. The i-th character of the string s denotes the color of the i-th ball (we'll number the balls from top to bottom of the stack). If the character is "R", the color is red. If the character is "B", the color is blue.


-----Output-----

Print the maximum number of operations ainta can repeatedly apply.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
3
RBR

Output
2

Input
4
RBBR

Output
6

Input
5
RBBRR

Output
6



-----Note-----

The first example is depicted below.

The explanation how user ainta applies the first operation. He pops out one red ball, changes the color of the ball in the middle from blue to red, and pushes one blue ball.

 [Image] 

The explanation how user ainta applies the second operation. He will not pop out red balls, he simply changes the color of the ball on the top from blue to red.

 [Image] 

From now on, ainta can't apply any operation because there are no blue balls inside the stack. ainta applied two operations, so the answer is 2.

The second example is depicted below. The blue arrow denotes a single operation.

 [Image]

Difficulty: MEDIUM

Starter code:

Solutions:
n = int(input())
balls = list(input())
balls.reverse()
stack = []
c = 0
pred = balls[0]
for b in balls:
	if b == pred:
		c += 1
	else:
		stack.append([pred, c])
		c = 1
	pred = b
else:
	stack.append([pred, c])
cnt = 0
l = len(balls)
while True:
	if stack[-1][0] == 'R':
		l -= stack[-1][1]
		stack.pop()
	else:
		k = stack[-1][1]
		cnt += 2 ** k - 1
		stack.pop()
		if stack:
			stack[-1][1] += k
		else:
			stack.append(['R', k])
		continue
	if not stack:
		break
	stack[-1][1] -= 1
	if stack[-1][1] == 0:
		stack.pop()
	if not stack:
		stack.append(['R', 1])
	elif stack[-1][0] == 'R':
		stack[-1][1] += 1
	else:
		stack.append(['R', 1])
	if l < n:
		stack.append(['B', n - l])
	l = n
	cnt += 1
print(cnt)


size = int(input())
stack = list(input())
res = 0
for i in range(size):
	if stack[i] == 'B':
		res += 2 ** i
print(res)


import math
import cmath
from typing import List, Any
n = int(input())
cnt = 0
s = list(input())
for x in range(n):
	if s[x] == 'B':
		cnt += pow(2, x)
print(cnt)


n = int(input())
st = input()
st = st[-1::-1]
st = st.replace('R', '0')
st = st.replace('B', '1')
print(int(st, 2))


n = int(input())
input_str = input()
count_op = 0
count = 0
for c in input_str:
	if c == 'B':
		count_op += 2 ** count
	count += 1
print(count_op)


length_stack = int(input())
stack = input()
sum = 0
for i in range(length_stack):
	if stack[i] == 'B':
		sum += pow(2, i)
print(sum)


n = int(input())
s = input()
new = []
for ele in s:
	if ele == 'R':
		new.append(0)
	else:
		new.append(1)
ans = 0
for i in range(n):
	if new[i] == 1:
		element = new[i] * 2 ** i
		ans += element
print(ans)


n = int(input())
s = list(input())
numberOfOp = 0
for i in range(n):
	if s[i] == 'B':
		numberOfOp = numberOfOp + 2 ** i
print(numberOfOp)


n = input()
s = input()
answ = 0
k = 0
for i in range(len(s)):
	if s[i] == 'B':
		answ += 2 ** i
print(answ)


n = int(input())
s = input()
ans = 0
for i in range(len(s)):
	if s[i] == 'B':
		ans += 2 ** i
print(ans)


input()
print(int(''.join(('0' if c == 'R' else '1' for c in input()[::-1])), 2))


numberOfBalls = int(input())
balls = input()
indecesOfBlueBalls = []
for k in range(len(balls)):
	if balls[k] == 'B':
		indecesOfBlueBalls.append(k)
needToSum = []
for k in range(len(indecesOfBlueBalls)):
	needToSum.append(2 ** indecesOfBlueBalls[k])
print(sum(needToSum))


def do():
	n = int(input())
	stack = [s for s in input()][::-1]
	b = stack.count('B')
	res = 0
	while b > 0:
		while stack and stack[-1] == 'R':
			stack.pop()
		stack[-1] = 'R'
		b -= 1
		if len(stack) < n:
			res += (1 << n - len(stack)) - 1
			stack += ['R'] * (n - len(stack))
		res += 1
	return res
print(do())


input()
print(int(input()[::-1].translate(str.maketrans('RB', '01')), 2))


import math, string, itertools, fractions, heapq, collections, re, array, bisect
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict

def main(n, s):
	if 'B' not in s:
		print(0)
		return
	b = s.count('B')
	r = s.count('R')
	op = {}
	op[0] = 1
	op[1] = 2
	op[2] = 4
	op[3] = 1 + op[2] + op[1] + op[0]
	op[3] = 8
	op[4] = 1 + op[3] + op[2] + op[1] + op[0]
	op[4] = 16
	ans = 0
	for (i, x) in enumerate(s):
		if x == 'B':
			ans += 2 ** i
	print(ans)

def main_input(info=0):
	n = int(input())
	s = input()
	main(n, s)

def __starting_point():
	main_input()
__starting_point()


import re
n = int(input())
s = [1 if x == 'B' else 0 for x in list(input())]
print(sum([el * 2 ** i for (i, el) in enumerate(s)]))


n = int(input())
stack = list(input())
i = 0
result = 0
while i < n:
	if stack[i] == 'B':
		result += 2 ** i
	i += 1
print(result)


s = input()
n = int(s)
s = input()
x = s
ans = 0
for i in range(0, n):
	if x[i] == 'B':
		ans += 1 << i
print(ans)


n = int(input())
string = input()
sum = 0
for i in range(len(string)):
	if string[i] == 'B':
		sum += 2 ** i
print(sum)


size = int(input())
stack = list(input())
print(sum([2 ** i for i in range(size) if stack[i] == 'B']))


n = int(input())

def f(x):
	if x == 'R':
		return '1'
	else:
		return '0'
print(2 ** n - 1 - int(''.join([f(c) for c in reversed(input())]), base=2))


n = int(input())
str = input()
if n == 1:
	if str == 'R':
		print('0')
	else:
		print('1')
else:
	sum = 0
	i = 0
	while i <= n - 1:
		if str[i] == 'B':
			sum += pow(2, i)
		i += 1
	print(sum)


(n, s) = (int(input()), input())
print(sum((2 ** i for i in range(n) if s[i] == 'B')))


n = int(input())
s = ''.join(('1' if c == 'R' else '0' for c in input()[::-1]))
d = int(s, 2)
print((1 << n) - 1 - d)


n = int(input())
s = input()
t = '_'.join(s)
w = t.split(sep='_')
a = 0
if w.count('B') == 0:
	print('0')
else:
	b = w.count('B')
	for i in range(b):
		c = w.index('B')
		a += 2 ** c
		w[c] = 'R'
	print(a)


def task_399A(n, p, k):
	ans = ''
	if p - k > 1:
		ans += '<< '
		for i in range(p - k, p):
			ans += str(i)
			ans += ' '
	else:
		for i in range(1, p):
			ans += str(i)
			ans += ' '
	ans += '({:d})'.format(p)
	if p + k < n:
		for i in range(p + 1, p + k + 1):
			ans += ' '
			ans += str(i)
		ans += ' >>'
	else:
		for i in range(p + 1, n + 1):
			ans += ' '
			ans += str(i)
	return ans

def task_399B(n, row):
	val = 0
	for c in row:
		val <<= 1
		if c == 'B':
			val += 1
	return val
n = int(input())
row = input()[::-1]
print(task_399B(n, row))


n = int(input())
s = input()
arr = [0] * n
record = [-1] * (n + 1)

def rec(n):
	if record[n] != -1:
		return record[n]
	else:
		l = 0
		for i in range(0, n):
			l += rec(i)
		record[n] = l + 1
		return record[n]
record[0] = 1
total = 0
for i in range(len(s)):
	if s[i] == 'B':
		total += rec(i)
print(total)


input()
color = input()
operations = 0
for i in range(0, len(color)):
	if 'B' in color[i]:
		operations += pow(2, i)
print(operations)


n = int(input())
s = list(input())
o = 0
try:
	index = s.index('B')
	o += pow(2, index)
	while True:
		index = s.index('B', index + 1)
		o += pow(2, index)
except:
	print(o)


inp = int(input())
balls = input()
tms = 1
ans = 0
for i in range(inp):
	if balls[i] == 'B':
		ans += tms
	tms *= 2
print(ans)


n = int(input())
s = input()
ans = 0
b = [0] * 50
b[0] = 1
for i in range(50):
	b[i] = 2 * b[i - 1] + 1
for i in range(n):
	if s[i] == 'B':
		ans += 1
		if i > 0:
			ans += b[i - 1]
print(ans)


input()
print(int(input().replace('R', '0').replace('B', '1')[::-1], 2))


input()
print(int(''.join(list(map(lambda x: '0' if x == 'R' else '1', input()[::-1]))), 2))


n = int(input())
strlist = list(input())
sum = 0
for i in range(n):
	if strlist[i] == 'B':
		sum += 2 ** i
print(sum)


n = int(input())
s = input()
print(sum(map(lambda i: 2 ** i * (s[i] == 'B'), range(n))))


n = int(input())
s = input()
res = 0
pow2 = [1 << i for i in range(51)]
for i in range(n):
	if s[i] == 'B':
		res += pow2[i]
print(res)


import sys

def main():
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().rstrip()
	res = 0
	for (i, c) in enumerate(s):
		if c == 'B':
			res |= 1 << i
	print(res)
main()


n = int(input())
B = input()
ans = 0
for i in range(n - 1, -1, -1):
	ans = ans * 2 + int(B[i] == 'B')
print(ans)


n = int(input())
str = input()
num = 0
for i in range(len(str)):
	if str[i] == 'B':
		num = num + pow(2, i)
print(num)


n = input()
s = input()
num = [0 if letter == 'R' else 1 for letter in s]
print(int(''.join(map(str, num[::-1])), 2))


def balls(s, n):
	result = 0
	step = [1 << i for i in range(51)]
	for j in range(n):
		if s[j] == 'B':
			result += step[j]
	return result
m = int(input())
t = input()
print(balls(t, m))


n = int(input())
s = input()
print(int(s[::-1].replace('R', '0').replace('B', '1'), base=2))


n = int(input())
s = input().strip()
op_cnt = 0
for i in range(n):
	if s[i] == 'B':
		op_cnt += 2 ** i
print(op_cnt)


n = int(input())
s = map(lambda x: 1 if x == 'B' else 0, list(input()))
print(sum([el * 2 ** i for (i, el) in enumerate(s)]))


n = int(input())
S = input()
an = 0
for i in range(len(S)):
	if S[i] == 'B':
		an += 2 ** i
print(an)


n = int(input())
s = input()
res = 0
l1 = [1]
l2 = [1]
res = 0
for i in range(1, n + 1):
	l1.append(l2[i - 1] + 1)
	l2.append(l2[i - 1] + l1[i])
	if s[i - 1] == 'B':
		res += l1[i - 1]
print(res)


(n, b) = (input(), input().replace('R', '0').replace('B', '1'))
print(int(b[::-1], 2))


n = int(input())
s = input()
count = 0
for i in range(n):
	if s[i] == 'B':
		count += 2 ** i
print(count)


def operation(l):
	try:
		ind = l.index('B')
		if ind == 0:
			b_counter = 0
			while l[b_counter] != 'R':
				l[b_counter] = 'R'
				b_counter += 1
				if b_counter == len(l):
					break
			return 2 ** b_counter - 1 + operation(l)
		else:
			for c in range(ind):
				l[c] = 'B'
			l[ind] = 'R'
			return 1 + operation(l)
	except:
		return 0
n = int(input())
s = input()
stack = list(s)
print(operation(stack))


n = int(input())
rb = input()
res = 0

def b_to_dec(rb):
	c = 0
	res = 0
	for i in rb:
		if i == 'B':
			res += 2 ** c * 1
		c += 1
	return res
res = b_to_dec(rb)
print(res)


def main():
	n = int(input())
	_array = list(input())
	ans = 0
	for _ in range(len(_array)):
		if _array[_] == 'B':
			ans += 2 ** _
	print(ans)
main()


n = int(input())
s = input().split()[0]
res = 0
for i in range(len(s)):
	if s[i] == 'B':
		res += 2 ** i
print(res)


n = int(input())
word = str(input())
res = 0
for i in range(len(word)):
	if word[i] == 'B':
		res |= 1 << i
print(res)


n = int(input())
s = input()
ops = 2 ** n - 1
for i in range(n):
	if s[i] == 'R':
		ops -= 2 ** i
print(ops)


def solve(stack):
	return sum([2 ** i for (i, c) in enumerate(stack) if c == 'B'])

def main():
	_ = int(input())
	stack = input()
	print(solve(stack))
main()


(length, string) = (int(input()), input())
print(sum([2 ** i if string[i] == 'B' else 0 for i in range(len(string))]))


n = int(input())
s = input()
tot = 0
for (i, ball) in enumerate(s):
	if ball == 'B':
		tot += 1 << i
print(tot)


n = int(input())
balls = str(input())
ans = sum((2 ** i for i in range(n) if balls[i] == 'B'))
print(ans)


n = int(input())
s = list(input())
count = 0
ans = [1]
for i in range(50):
	ans.append(sum(ans) + 1)
for i in range(n):
	char = s[i]
	if char == 'B':
		count += ans[i]
print(count)


n = int(input())
s = str(input())
su = 0
j = 0
a = -1
for i in range(n):
	if s[i] == 'R':
		a = 1
	else:
		a = 0
	su += a * pow(2, j)
	j += 1
print(pow(2, j) - 1 - su)


def calculate(n, s):
	c = 0
	for i in range(len(s)):
		if s[i] == 'B':
			c += pow(2, i)
	return c
n = input()
s = input()
print(calculate(int(n), s))


n = int(input())
s = input()
ans = 0
for i in range(len(s)):
	ch = s[i]
	if ch == 'B':
		ans |= 1 << i
print(ans)


n = int(input())
s = input()
ans = 0
count = count1 = 0
w = 0
for i in range(n):
	if s[i] == 'R':
		if w == 0:
			ans += 2 ** count - 2 ** (count - count1)
		count1 = 0
		w = 1
	else:
		w = 0
		count1 += 1
	count += 1
if s[-1] == 'B':
	ans += 2 ** count - 2 ** (count - count1)
print(ans)