Problem Statement

There are $N$ squares arranged in a row. The $i$-th square from the left is called square $i$.

Some squares have traps set on them, and the states of the squares are represented by a string $S$ of length $N$. $S_i$ corresponds to square $i$, where '.' means there is no trap and '#' means there is a trap.

stop-kun is currently standing on square $1$ and wants to go to square $N$.
In addition, stop-kun has a variable $x$ (initially $1$), and can "save" his current location to $x$.

Until he stops exactly on square $N$, stop-kun repeatedly chooses at random one of the following 3 types of operations and performs it. Here, the 3 types of operations are equally likely and are chosen independently each time.

• Move 1 square to the right. If he goes past square $N$ or stops exactly on a '#' square, the game is over and he is sent to square $x$.
• Move 2 squares to the right. If he goes past square $N$ or stops exactly on a '#' square, the game is over and he is sent to square $x$.
• Save. If he is currently on square $i$, update $x \leftarrow i$.

Find the expected number of operations performed (the total over the 3 types).

Under the constraints of this problem, the expected value is always defined. It can also be proved that the answer does not exceed $10^9$ under these constraints.

Input

$N$
$S$

• $N$ is an integer.
• $2 \leq N \leq 2 \times 10^5$
• $S$ is a string of length $N$ consisting only of '.' and '#'.
• $S_1$ and $S_N$ are '.'.
• In $S$, '#' does not appear 2 or more times in a row.

Output

Output the expected number of operations performed (the total over the 3 types).

Your answer is considered correct if its absolute or relative error from the expected answer is at most $10^{-5}$.

Sample

2
..

3

4
..#.

7.5

10
.#...#..#.

23.130836237