Problem I
IMO Harder Problem

After passing the final round of the Hunter Exam, Gon is now a Hunter! But before continuing his exciting journey, Gon decides to visit his home in ‘While Island’.

Aunt Mito is happy that Gon has become a Hunter and has visited home. But at the same time, she feels worried about Gon — the life of a Hunter is challenging. Thus, she will not allow Gon to leave ‘While Island’, unless Gon is able to solve a puzzle prepared by aunt Mito.

But what puzzle should Mito give to Gon? Mito opened ‘IMO 2019 Problems’ and found the following problem:

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Prof. Tuy has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k>0$ coins showing $H$, then he turns over the $k$-th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n=3$ the process starting with the configuration $THT$ would be: $THT\to HHT\to HTT\to TTT$, which stops after three operations.

Show that, for each initial configuration, Prof. Tuy stops after a finite number of operations.

‘This problem is too easy’ — Mito thought. ‘Gon will be able to solve it in no time’.

After some more thinking, Mito changed the above problem to the following harder version:

For each initial configuration $C$, let $L(C)$ be the number of operations before Prof. Tuy stops.

Given a sequence $S$ consisting of $H$, $T$ and $?$, representing some initial state, where $?$ denotes an unknown state. Calculate the average value of $L(C)$ over all possible sequences $C$ represented by $S$.

Even though Gon is smart, he is still unable to solve this question. Please help Gon!

Input

The input contains a single non-empty line with at most ${10}^6$ characters — the sequence $S$.

Output

The output must contain a single number — the average value of $L(C)$, as explained in the statement.

Your answer will be considered correct if its relative or absolute error doesn’t exceed ${10}^{-6}$.

Namely: let’s assume that your answer is $a$, and the answer of the jury is $b$. The checker program will consider your answer correct, if $\frac{|a-b|}{max(1,b)}\le {10}^{-6}$.

HH

2.0

H?

1.5

??

1.5