問題文

$N$ 個のマスが一列に並んでいます。左から $i$ 番目のマスをマス $i$ と呼びます。

いくつかのマスには罠が仕掛けられており、マスの状態は長さ $N$ の文字列 $S$ で表されます。 $S_i$ はマス $i$ に対応し、'.' は罠がないことを、'#' は罠があることを表します。

stop くんは現在マス $1$ に立っていて、マス $N$ に行きたいです。
さらに stop くんは変数 $x$ （初期値は $1$）を持っており、$x$ に現在の居場所を「セーブ」することができます。

stop くんはマス $N$ にちょうど止まるまで、次の3種類の操作のいずれかを無作為に選び行うことを繰り返します。 ここで3種類の操作は等確率で、かつ毎回独立に選ばれるものとします。

• 右方向に1マス進む。マス $N$ を超えた場合や '#' のマスにちょうど止まった場合はゲームオーバーとなり、マス $x$ に飛ばされる。
• 右方向に2マス進む。マス $N$ を超えた場合や '#' のマスにちょうど止まった場合はゲームオーバーとなり、マス $x$ に飛ばされる。
• セーブする。現在マス $i$ にいるとして、$x \leftarrow i$ と更新する。

このとき、操作を行う回数（3種類の合計）の期待値を求めてください。

本問題の制約下において、期待値は必ず定義されます。また、この制約下で解は $10^9$ を超えないことが証明できます。

入力

$N$
$S$

• $N$ は整数
• $2 \leq N \leq 2 \times 10^5$
• $S$ は '.' と '#' のみから成る長さ $N$ の文字列
• $S_1$ と $S_N$ は '.'
• $S$ において '#' は2文字以上連続しない

出力

操作を行う回数（3種類の合計）の期待値を出力してください。

想定解答との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解とみなされます。

サンプル

2
..

3

4
..#.

7.5

10
.#...#..#.

23.130836237