D - Christmas 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400

問題文

とある世界では、今日はクリスマスです。

高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L0 以上の整数) とは次のようなものです。

  • レベル 0 バーガーとは、パティ 1 枚である。
  • レベル L バーガー (L \geq 1) とは、バン 1 枚、レベル L-1 バーガー、パティ 1 枚、レベル L-1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。

例えば、パティを P、バンを B で表すと、レベル 1 バーガーは BPPPB (を 90 度回転したもの)、レベル 2 バーガーは BBPPPBPBPPPBB といった見た目になります。

高羽氏が作るのはレベル N バーガーです。ダックスフンドのルンルンは、このバーガーの下から X 層を食べます (パティまたはバン 1 枚を 1 層とします)。ルンルンはパティを何枚食べるでしょうか?

制約

  • 1 \leq N \leq 50
  • 1 \leq X \leq ( レベル N バーガーの層の総数 )
  • N, X は整数である。

入力

入力は以下の形式で標準入力から与えられる。

N X

出力

レベル N バーガーの下から X 層に含まれるパティの枚数を出力せよ。


入力例 1

2 7

出力例 1

4

レベル 2 バーガー (BBPPPBPBPPPBB) の下から 7 層にはパティが 4 枚含まれます。


入力例 2

1 1

出力例 2

0

レベル 1 バーガーの一番下の層はバンです。


入力例 3

50 4321098765432109

出力例 3

2160549382716056

レベル 50 バーガーは層の数が 32 ビット整数に収まらない程度に分厚いです。

Score : 400 points

Problem Statement

In some other world, today is Christmas.

Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:

  • A level-0 burger is a patty.
  • A level-L burger (L \geq 1) is a bun, a level-(L-1) burger, a patty, another level-(L-1) burger and another bun, stacked vertically in this order from the bottom.

For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.

The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?

Constraints

  • 1 \leq N \leq 50
  • 1 \leq X \leq ( the total number of layers in a level-N burger )
  • N and X are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.


Sample Input 1

2 7

Sample Output 1

4

There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB).


Sample Input 2

1 1

Sample Output 2

0

The bottom-most layer of a level-1 burger is a bun.


Sample Input 3

50 4321098765432109

Sample Output 3

2160549382716056

A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.