题目描述

你在黑板上写了一个长度为 n 的字符串。字符串中的字符只有两种，要么是 0 ，要么是 1 。

字符串有一个代价，计算方式如下：

假如把 1 看成隔板，则字符串被分隔成一段一段连续的 0。

我们称一段连续的 0 为一个 Zero 串。

如果一个 Zero 串中 0 的个数为 k，则该 Zero 串的得分为 $k^2$。

字符串的代价就是其中所有的 Zero 串的得分之和。

例如：0001100001 的代价就是 $3^2+4^2=9+16=25$。

后来，不知道谁擦黑板，把其中的一些字符给擦掉了。

被擦掉的地方可能是 0，也可能是 1。

遗憾的是，你已经记不清自己开始到底写的是什么了。

我们只好认为这些被擦掉的字符，有一半的可能是 0 ,有一半的可能是 1。

那么这个字符串的期望代价是多少呢？

输入格式

第一行：一个整数 n，表示字符串的长度

接下来一行：一个字符串，每个字符要么是 0 ，要么是 1，要么是 ? （表示被擦掉的字符）。

输出格式

一个实数，表示期望代价，四舍五入保留 4 位小数。

样例输入1

5
00?11

样例输出1

6.5000

样例1解释

00?11

? 是 0：00011 ===> $3^2=9$

? 是 1：00111 ===> $2^2=4$

期望 = (9+4)/2 = 6.5000

样例输入2

4
????

样例输出2

4.1250

数据规模

n<=300000