В каком-то другом мире сегодня 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-битное целое число. |