Description

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

DNA 序列可以用由四个字母 ‘A’、‘G’、‘C’ 和 ‘T’ 组成的字符串表示。一个 DNA 模式 是一个由这四个字母加上 ‘?’ 组成的字符串。如果模式中的每个字符要么是 ‘?’，要么与 DNA 序列中对应位置的字符相同，我们就说该 DNA 模式匹配一个相同长度的 DNA 序列。例如，模式 “AC?” 匹配 DNA 序列 “ACA”、“ACG”、“ACC” 和 “ACT”。

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

Input Format

输入由单个测试用例组成，格式如下。

输入的第一行包含两个正整数 $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’ 和 ‘?’ 组成。

Output Format

设 $S$ 是一个均匀随机选择的长度为 $n$ 的 DNA 序列。设 $w$ 为 $S$ 与 $P_1, \dots, P_m$ 中至少一个匹配的概率。输出是一个近似 $w$ 的实数 $v$。

如果 $v$ 在 $5\%$ 的乘法误差范围内近似 $w$，即

则判断输出 $v$ 正确。

$v$ 可以用指数部分表示，也可以不用。例如，$0.045$ 可以表示为 $4.5\text{e}-2$ 或 $0.045$。

3 1
AC?

0.0625

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

0.0302734375

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

8.673617379884035e-19

Hint

在第一个样例中，长度为 3 的 DNA 序列有 $4^3$ 种。有 4 个 DNA 序列 “ACA”、“ACG”、“ACC” 和 “ACT” 匹配模式 “AC?”。因此，概率为 $4/4^3 = 0.0625$。任何介于 $0.059375$ 和 $0.065625$ 之间的实数都被接受为正确输出。

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

翻译由 DeepSeek V3 完成