Expected Score in Simplified Osu

You are given a string representing a sequence of n clicks in a simplified version of the osu game. Each click is represented by one of the following characters:

• o: a successful click.
• x: a failed click.
• ?: an uncertain click that is o or x with equal probability (50% each).

The scoring rule is based on combos. A combo is defined as a maximal contiguous substring of o characters. If a combo has length \(a\), it contributes \(a^2\) to the score. For example, the string ooxxxxooooxxx has two combos: one of length 2 and one of length 4, so the total score is \(2^2 + 4^2 = 4 + 16 = 20\).

When the input string contains ? characters, they are replaced independently by o or x with equal probability. Your task is to calculate the expected score of the game.

Example: For input oo?xx, if the ? is replaced by o the string becomes oooxx with a score of \((3^2)=9\); if replaced by x the string becomes ooxxx with a score of \((2^2)=4\). Thus, the expected score is \((9+4)/2 = 6.5\).

inputFormat

The input consists of a single line containing a string s (with characters o, x, and ?) representing the sequence of clicks.

It is guaranteed that the string is non-empty.

outputFormat

Output a number representing the expected score. The answer will be considered correct if it is accurate up to an absolute or relative error of at most 10^{-6}.

sample

oo?xx

6.5