题目描述

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

高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル $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$ 層とします)。ルンルンはパティを何枚食べるでしょうか？

输入格式

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

$N$ $X$

输出格式

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

题目大意

有这样一种字符串 $str_i$：

• 当 $i=0$ 时，$str_i=\verb!P!$。
• 当 $i>0$ 时，$str_i=\verb!B!+str_{i-1}+\verb!P!+str_{i-1}+\verb!B!$。

求字符串为 $str_n$ 的前 $x$ 个字符中有多少个为 $p$。

2 7

4

1 1

0

50 4321098765432109

2160549382716056

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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