A string $s$ is called a DNA sequence if and only if $s$ consists only of A, C, G, and T.

Given $m$ strings $s_1, \dots, s_m$, each of length $n$, consisting only of A, C, G, T, and ?.

For a DNA sequence $t$ of length $n$, $t$ is called valid if and only if there exists some $s_i$ and a way to replace the ? characters in $s_i$ such that the resulting string $\tilde{s}_i$ is equal to $t$.

You need to calculate the probability that $t$ is valid, assuming $t$ is chosen uniformly at random from all DNA sequences of length $n$.

Your answer will be considered correct if the relative error does not exceed $5\%$. In other words, if the true probability is $w$ and you output $v$, your answer is correct if and only if $0.95w \le v \le 1.05w$.

Input

The first line contains two positive integers $n$ and $m$.

The next $m$ lines each contain a string $s_i$ of length $n$, guaranteed to consist only of A, C, G, T, and ?.

Output

A single line containing a real number representing the answer.

You may use scientific notation. For example, $\texttt{0.045}$ can also be output as $\texttt{4.5e-2}$.

Examples

Input 1

3 1
AC?

Output 1

0.0625

Note 1

Any real number in the interval $[0.059375, 0.065625]$ will be accepted as a correct answer.

The sample output is guaranteed to have a relative error of no more than $1\%$ from the true answer.

Input 2

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

Output 2

0.0302734375

Input 3

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Output 3

8.673617379884035e-19

Note 3

Outputting $0$ here is incorrect because the relative error is being evaluated.

Note that as $n$ becomes larger, the answer can become smaller. You may consider using long double and outputting with printf("%.70Lf\n", ans).

Input 4

See the provided files. This sample satisfies $w \ge 0.01$.

Input 5

See the provided files. This sample satisfies $n=100$, and the number of ? in $s_i$ is uniformly random in $[0, n-20]$.

Input 6

See the provided files.

Constraints

For $30\%$ of the data, $m \le 20$.

For another $20\%$ of the data, the true answer $w \ge 0.01$.

For another $20\%$ of the data, $n=100$, and the number of ? in $s_i$ is uniformly random in $[0, n-20]$.

For $100\%$ of the data, $1 \le n \le 100, 1 \le m \le 40$.

Due to certain reasons, the last $30\%$ of the data is tested as a bundle.