问题文

高桥君喜欢无刻印键盘。今天，他准备用一台只有字母和数字的键帽的键盘来打字。

然而，高桥君并没有完全记住键盘的布局。对于他记得的字符，他只需要按下对应的键。对于他忘记的字符，他只能随便选择一个键，如果选错了，他就必须使用退格键进行删除。

高桥君试图输入一段文本 $S$。为了尽可能减少按键次数的期望值，高桥君可以记住每次按下哪个键所对应的字符，并根据这些信息来选择下一个按键。

请计算在高桥君采取最优策略的情况下，按键的期望次数。

注意，我们假设高桥君记得退格键的位置以及除了字母和数字之外的所有键。

此外，我们假设不能改变输入位置，比如箭头键或者鼠标操作。

输入

从标准输入中按以下格式给出输入。

$S$ $K$

• 第一行是想要输入的字符串 $S (1 ≦ |S| ≦ 50)$。字符串 $S$ 只包含小写字母和数字。
• 第二行是高桥君记得的键的种类，由字符串 $K$ 表示。字符串 $K$ 可以通过从1234567890abcdefghijklmnopqrstuvwxyz中选择一个字符并重复任意次数而得到，保证字符串 $K$ 的第一个字符为1。

输出

请以一行输出高桥君需要按键的期望次数，末尾记得换行。

输出的绝对误差或相对误差应不超过 $10^{-6}$。

输入例子1

takahashikun
1234567890abcdefghijklmnopqrstuvwxyz

输出例子1

12

由于高桥君记住了所有键，所以他按下键的次数就是12，与字符串takahashikun的长度相同。

输入例子2

p
1234567890abcdefghijklmnorstuvwxyz

输出例子2

2

高桥君忘记了p和q这两个键的位置。为了按下p，他需要按下这两个未知键中的一个。

• 当按下p时，句子完成。因此，高桥君按键总数为 $1$。
• 当按下q时，他发现另一个键是p。因此，他需要使用退格键删除一个字符，并再次按下p键，以完成句子。在这种情况下，高桥君按键次数为 $3$。

由于这两种情况是等概率发生的，所以按键次数的期望值为 $2$。

题目来源

Code Formula 2014 预选A