配点 : $400$ 点

問題文

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

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

• レベル $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$ 層に含まれるパティの枚数を出力せよ。

2 7

4

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

1 1

0

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

50 4321098765432109

2160549382716056

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