题目描述

潜在癌症调查中心（ICPC）发现了导致癌症的 DNA 序列模式！我们希望你编写一个计算机程序，近似计算一个随机 DNA 序列匹配给定模式之一的概率。

DNA 序列可以表示为由四个字母组成的字符串：'A'、'G'、'C' 和 'T'。DNA 模式是由相同的四个字母加上 '?' 组成的字符串。如果 DNA 模式与长度相同的 DNA 序列匹配，当且仅当模式中的每个字符要么是 '?'，要么与 DNA 序列中对应位置的字符相同。例如，模式 "AC?" 匹配 DNA 序列 "ACA"、"ACG"、"ACC" 和 "ACT"。

你的任务是编写一个程序，给定一组相同长度的 DNA 模式，计算长度相同的均匀随机 DNA 序列匹配给定模式之一的概率。允许有最多 $5\%$ 的相对误差。

输入

输入由一个测试用例组成，格式如下：

第一行包含两个正整数 $n$ 和 $m$，满足 $1 \leq n \leq 100$ 且 $1 \leq m \leq 30$。接下来的 $m$ 行包含 $m$ 个模式 $P_1, \dots, P_m$。每个模式 $P_i$ 是一个长度为 $n$ 的字符串，由字符 'A'、'G'、'C'、'T' 和 '?' 组成。

输出

设 $S$ 为长度为 $n$ 的均匀随机 DNA 序列。设 $w$ 为 $S$ 匹配至少一个模式 $P_1, \dots, P_m$ 的概率。输出一个实数 $v$，近似计算 $w$。

当 $v$ 近似 $w$ 的相对误差在 $5\%$ 以内，即：

则认为输出 $v$ 是正确的。

$v$ 可以用带有或不带指数形式表示。例如，$0.045$ 可以表示为 $4.5e-2$ 或 $0.045$。

3 1
AC?

0.0625

6 2
AC??A?
A??A?T

0.0302734375

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

8.673617379884035e-19

样例解释

在第一个样例中，长度为 $3$ 的 DNA 序列共有 $4^3$ 种。匹配模式 "AC?" 的 DNA 序列有 $4$ 种，分别是 "ACA"、"ACG"、"ACC" 和 "ACT"。因此，概率为：

任何介于 $0.059375$ 和 $0.065625$ 之间的实数都被接受为正确的输出。

正如第三个样例所示，概率可能是一个非常小的实数。注意，0 不是正确的输出，因为 $0$ 小于精确概率的 $95\%$。