题目描述

The Investigation Center for Potential Cancer (ICPC) found out patterns of a DNA sequence that cause cancer! We would like you to write a computer program that approximates the probability that a random DNA sequence matches one of the given patterns.

A DNA sequence can be represented by a string consisting of four letters, ‘A’, ‘G’, ‘C’, and ‘T’. A DNA pattern is a string over the same four letters plus ‘?’. We say that a DNA pattern matches a DNA sequence of the same length if each of the characters in the pattern is either ‘?’ or is the same as the character at the corresponding position in the DNA sequence. For example, a pattern “AC?” matches DNA sequences “ACA”, “ACG”, “ACC”, and “ACT”.

Your task is to write a program that, given a set of DNA patterns of the same length, computes the probability that a uniformly random DNA sequence of the same length matches any of the given patterns. A multiplicative error up to $5\%$ is permissible.

输入格式

The input consists of a single test case of the following format.

$$n\ m$$ $$P_1$$ $$\vdots$$ $$P_m$$

The first line of the input contains two positive integers $n$ and $m$ such that $1 \leq n \leq 100$ and $1 \leq m \leq 30$ hold. The next $m$ lines contain $m$ patterns $P_1, \dots, P_m$. Each pattern $P_i$ is a string of length $n$ over ‘A’, ‘G’, ‘C’, ‘T’, and ‘?’.

输出格式

Let $S$ be a DNA sequence of length $n$ chosen uniformly at random. Let $w$ be the probability that $S$ matches at least one of $P_1, \dots, P_m$. The output is a real number $v$ that approximates $w$.

The output $v$ is judged to be correct if $v$ approximates $w$ within a multiplicative error of $5\%$, i.e.,

$$0.95 \times w \leq v \leq 1.05 \times w$$

$v$ should be represented either with or without exponent component. For example, $0.045$ can be represented as $4.5\text{e}-2$ or $0.045$.

3 1
AC?

0.0625

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

0.0302734375

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

8.673617379884035e-19

提示

In the first sample, there are $4^3$ DNA sequences of length 3. There are 4 DNA sequences, “ACA”, “ACG”, “ACC”, and “ACT”, that match the pattern “AC?”. Thus, the probability is $4/4^3 = 0.0625$. Any real number between $0.059375$ and $0.065625$ is accepted as a correct output.

As in the third sample, the probability can be a small real number. Note that “0” is not a correct output, as $0$ is less than $95\%$ of the precise probability.