题目描述

你进入了一档游戏节目的最后一轮，现在要决定最终奖金的数额。奖金由一个十进制数表示，其位数已经确定。

在完整的游戏过程中，你会依次得到若干个随机数字。每次得到一个数字后，必须立即把它放入当前尚未填写的某一位中；在看到下一个数字之前就必须做出决定，并且已经放置的数字不能移动。所有空位填完后，得到的十进制数就是最终奖金。

现在给出当前数字板的状态。字符串中的字符 0 到 9 表示该位置已经填入对应数字，字符 _ 表示该位置仍为空。之后每一步都会独立、等概率地产生 $0,1,\ldots,9$ 中的一个数字。

从当前状态开始，你会采用最优策略，使最终奖金的期望值尽可能大。求这个最大期望值。

注意，当前已经填入的数字不一定是按照最优策略得到的；只需要从当前状态开始最优决策。

输入格式

输入一行字符串 digits，表示当前数字板。

输出格式

输出一个实数，表示在最优策略下最终奖金的最大期望值。

答案的绝对误差或相对误差不超过 $10^{-9}$ 即可。

数据范围

• $1\le |digits|\le 50$；
• digits 只包含字符 _ 和 0 到 9。

样例 1

输入

_0

输出

45.0

解释

只剩一个空位，因此还会得到一个随机数字。最终结果可能为 $0,10,20,\ldots,90$，其平均值为 $45$。

样例 2

输入

__

输出

60.75

解释

当第一个数字为 $5,6,7,8,9$ 时，将其放在左边；当它为 $0,1,2,3,4$ 时，将其放在右边，可以取得最优期望值。

样例 3

输入

_55_

输出

6303.25

样例 4

输入

____0000000000000000

输出

7.482735000000001E19

样例 5

输入

___6__3___

输出

8.604871517066002E9

样例 6

输入

__________

输出

8.882477600592714E9