006 - &`∑´&

時間制限 1 秒 / メモリ制限 32 MB / 得点 1 / x 8 /


TLE
1sec
MLE
32MB
得点
1

問題

整数 $N,X$ が与えられるので、 $\displaystyle\sum_{i=0}^{N}$($2^i$ $\mbox{AND}$ $X$)を出力せよ。
なお、$A \ \mbox{AND} \ B \ $は$ \ A \ $と$ \ B \ $のビットごとの論理積を表します。

入力

$N$ $X$

出力

$\displaystyle\sum_{i=0}^{N}$($2^i$ $AND$ $X$)を出力せよ。
出力の末尾には改行を入れること。

制約

  • $0 \leq N \leq 60$
  • $0 \leq X \leq 2^{60}$
  • 入力は全て整数

入出力例

例1

入力

2 11

出力

3

解説

計算過程を二進数で表すと、

  • (i=0) 0001
  • (i=1) 0010
  • (i=2) 0000
0001 + 0010 + 0000 = 0011 となり、0011は十進数では3である。
ちなみに11は二進数では1011である。

例2

入力

18 546884135377750831

出力

314159