В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня
L
(
L
- целое число, большее или равное
0
) готовится следующим образом:
- Бургер нулевого уровня - это котлета.
- Бургер с уровнем
L
(L >= 1) - это булочка, бургер с уровнем (L-1
), котлета, бургер с другим уровнем (L-1
) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.
Например, бургер уровня 1 и бургер уровня 2 выглядят как
БКККБ
и
ББКККБКБКККББ
(повернутые на 90 градусов), где
Б
и
К
обозначают булочку и котлету.
Бургер, который приготовит дед Кокованя, - это бургер уровня
N
. Дарёна всегда съедает только
Х
слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?
Входные данные
Программа получает на вход 2 целых числа через пробел:
N
и
X
(1 <=
N
<= 50, 1 <=
X
<= (общее количество слоев в бургере
N
-го уровня)).
Выходные данные
Выведите количество котлет в самых нижних
X
слоях, считая от нижней части бургера уровня
N
.
Примеры
№ |
Входные данные |
Выходные данные |
Пояснение |
1 |
2 7 |
4 |
В самых нижних 7 слоях бургера второго уровня ( ББКККБКБКККББ ) находятся 4 котлеты. |
2 |
1 1 |
0 |
|
3 |
50 4321098765432109 |
2160549382716056 |
Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число. |