题目背景

在处理字符串时，如果一个字符串的后缀与另一个字符串的前缀相同，就可以让这两部分重叠，从而得到比直接拼接更短的字符串。

现在有两个包含未知字符的字符串。每个未知字符都会随机变成给定字母表中的某个字符。请计算替换完成后，两个字符串最短重叠连接长度的期望值。

题目描述

对于一个有序字符串对 $(A,B)$，若字符串 $S$ 同时满足：

• $A$ 是 $S$ 的前缀；
• $B$ 是 $S$ 的后缀；

则称 $S$ 是 $(A,B)$ 的一个重叠连接。

在所有重叠连接中，长度最短的称为 $(A,B)$ 的最短重叠连接，简称 SOC。

例如，当：

A = cabab
B = ababc

时，可以让 A 的后缀 abab 与 B 的前缀 abab 重叠，得到：

cababc

因此，cababc 是 $(A,B)$ 的最短重叠连接，其长度为 $6$。

形式化地，设 $|A|=|B|=n$。若最大的整数 $k$ 满足：

$$A[n-k\ldots n-1]=B[0\ldots k-1],$$

则最短重叠连接的长度为：

$$2n-k.$$

现在给定字符串 $A$、$B$ 和字符串 alphabet。

字符串 $A$ 和 $B$ 中：

• 普通小写字母表示该位置的字符已经确定；
• 字符 * 表示该位置是未知字符。

每一个 * 都会相互独立地从 alphabet 包含的字符中等概率选择一个字符。

例如，若：

alphabet = abc

则每个 * 分别有 $\frac13$ 的概率变成 a、b 或 c。

当所有 * 都完成替换后，$A$ 和 $B$ 都会变成确定的字符串。请计算此时 $(A,B)$ 的最短重叠连接长度的期望值。

输入格式

输入共三行。

第一行包含字符串 $A$。

第二行包含字符串 $B$。

第三行包含字符串 alphabet，表示未知字符可以选择的字母集合。

输出格式

输出一个实数，表示最短重叠连接长度的期望值。

若你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

数据范围

对于所有测试数据：

• $1\le |A|=|B|\le 32$；
• $1\le |\text{alphabet}|\le 26$；
• alphabet 只包含小写英文字母；
• alphabet 中的字符两两不同；
• $A$ 和 $B$ 中的每个字符要么是 *，要么属于 alphabet。

样例 1

输入

aa*aa
a*aaa
ab

输出

7.0

解释

两个 * 均可独立地变成 a 或 b，因此共有四种等概率情况：

$A$	$B$	最短重叠连接	长度
aaaaa	aaaaa	aaaaa	$5$
aabaa		aabaaaaa	$8$
aaaaa	abaaa	aaaaabaaa	$9$
aabaa		aabaaa	$6$

因此期望长度为：

$$\frac{5+8+9+6}{4}=7.$$

样例 2

输入

**
**
ab

输出

3.125

解释

两个字符串中一共有四个未知位置，因此共有：

$$2^4=16$$

种等概率替换结果。

其中：

• $4$ 种结果的最短重叠连接长度为 $2$；
• $6$ 种结果的长度为 $3$；
• $6$ 种结果的长度为 $4$。

因此答案为：

$$\frac{4\times2+6\times3+6\times4}{16}=3.125.$$

样例 3

输入

**a*cd
cde***
abcdefghijklmnopqrstuvwxyz

输出

10.0

解释

无论各个未知字符最终被替换成什么字符，最短重叠连接的长度始终为 $10$。

样例 4

输入

h*phz*
hzph*p
zph

输出

10.555555555555557

样例 5

输入

a*a*a*a*a*a*
*a*a*a*a*a*a
abcdef

输出

23.6983063804134