Description

最近科学家发现一种奇怪的单细胞生物，它的基因序列是由‘A’、‘C’、‘G’、‘T’四种字符组成的字符串，并且从它存在的第1天开始到第m天（0 < m <= 200）每天都会在末尾增加一个字符。增加‘A’的概率为a，‘C’的概率为c，‘G’的概率为g，‘T’的概率为t，a+c+g+t=1.0。 科学家还发现某些基因序列对这种单细胞生物是有害的，如果它的基因序列中出现了这些有害的基因序列，那么它将会立即死亡。 现给出n（0 < n <= 200）个有害的基因序列，m、a、c、g、t，以及单细胞生物最初的基因序列，求该生物在m天后还存活的概率。

Input

输入有多组数据。每组数据第一行两个整数n，m。第二行四个实数a，c，g，t。 接下来n行每行一个非空有害基因序列，长度<=15。最后一行一个非空字符串，表示单细胞生物最初的基因序列，长度<=50。每个基因序列只包括‘A’、‘C’、‘G’、‘T’四种字符，保证a+c+g+t=1.0。

Output

以百分比输出m天后该生物还存活的概率，保留2位小数。

Sample

Input

3 5
0.25 0.25 0.25 0.25
AC
AG
AT
CGT

Output

35.55%

Source: LGW