In some other world today is December 31st. Grandfather Kokovanya decided to cook a multi-dimensional burger that Daryon loves so much. A
L level burger (
L is an integer greater than or equal to
0) is being prepared in the following way:
- Level zero burger is a patty.
- Burger with level
L (L >= 1) is a bun, burger with level (L-1), cutlet, burger with another level (L-1) and another bun, stacked vertically in this order, counting from the bottom.
For example, a level 1 burger and a level 2 burger look like
BKKKB and
BBKKKBKBKKKBB (rotated 90 degrees), where
B and
K denote a bun and cutlet.
The burger that grandfather Kokovanya will cook is a level
N burger. Daryona always eats only
X layers of the bottom of the burger (a layer is a patty or a bun). How many meatballs will she eat?
Input
The program receives as input 2 numbers separated by a space:
N and
X.
Imprint
Output the number of cutlets in the bottom
X layers, counting from the bottom of the
N layer burger.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
2 7 |
4 |
In the bottom 7 layers of the second level burger ( BBKKKBKBKKKBB) there are 4 burgers. |
| 2 |
1 1 |
0 |
|
| 3 |
50 4321098765432109 |
2160549382716056 |
A level 50 burger is quite thick, so much so that the number of layers does not fit into a 32-bit integer. |