配点 : $500$ 点

問題文

すぬけくんは黒板に $1$ 以上 $(2^N-1)$ 以下の整数をすべて書きました． ただし，整数は $2$ 進表記で書きました．

黒板に書かれた整数を文字列として見た時，辞書順で $X$ 番目に小さい文字列を求めてください．

なお，入力において $N$ は $10$ 進法で与えられますが，$X$ は $2$ 進法で与えられます．

制約

• $1 \leq N \leq 10^6$
• $1 \leq X \leq 2^N-1$
• $X$ は $2$ 進法で与えられる．

入力

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

$N$

$X$

出力

答えを出力せよ．

3
101

11

黒板に書かれた文字列を辞書順に並べると，1,10,100,101,11,110,111 です． また $X=101(2\mathrm{進})=5(10\mathrm{進})$ です． よって，答えは 11 になります．

10
10100011

1001001111

1000000
11111

1000000000000000000000000000000