問題文

$1,2,\dots,N$ と番号がついた $N$ 枚のタイルがこの順に円環上に並んでいます。
各整数 $i\ (1\le i\le N-1)$ に対してタイル $i$ の右隣にはタイル $i+1$ があり、タイル $N$ の右隣にはタイル $1$ があります。

タイル $1$ を含むいくつかのタイルは黒く塗られていて、それ以外のタイルはまだ色が塗られていません。
それぞれのタイルの色の情報は、0, 1 からなる長さ $N$ の文字列 $s=s_1s_2\cdots s_N$ で次のように与えられます。

• 各整数 $i\ (1\le i\le N)$ に対して、タイル $i$ が黒く塗られているならば $s_i$ は 1 であり、塗られていないならば $s_i$ は 0 である。

最初、ユキさんがタイル $1$ のところにいます。 ユキさんは全てのタイルが黒く塗られるまで、次の一連の手順からなる動作を繰り返します。

• ユキさんが現在いるタイルの右隣と左隣のタイルのいずれかを等確率（$1/2$ ずつの確率）で選択し、そこに移動する。
• 移動先のタイルにまだ色が塗られていないならば、そのタイルを黒く塗る。

全てのタイルが黒く塗られるまでの動作回数の期待値を求めてください。
なお、この値は $10^{18}$ 以下の非負整数であることが制約から証明できます。

入力

$N$
$s$

• $2\le N\le 10^6$
• $N$ は整数である。
• $s$ は 0 と 1 のみからなる長さ $N$ の文字列である。
• $s_1$ は 1 である。
• $s$ は $1$ つ以上の 0 を含む。

出力

全てのタイルが黒く塗られるまでの動作回数の期待値を整数として出力してください。

サンプル

2
10

1

3
110

2

10
1000110010

41