Dengsh Loves Kebab

题号：NC232328
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

DSH loves kebab.

The restaurant has $N$ $(2 \leq N \leq 50)$ types of kebabs, each of which can be represented by a string of length $M$ $(1\leq M\leq 1000)$ consisting of lowercase letters.

The representing string is 1-indexed.

It is guaranteed that no two types of kebabs are the same.

DSH is a frequent visitor, therefore he knows the representing strings of all types of kebabs.

Today, DSH has just bought a kebab, which is wrapped in a opaque packing.

DSH missed the moment when the cook put kebab into the packing, so he does not know what type the kebab is.

However, he is sure that the kebab must be one of the $N$ types with equal probability.

DSH slowly takes the kebab out of the packing.

At moment $0$ , DSH knows nothing about the kebab's representing string.

At moment $K$ $(K \ge 1)$ , he will reveal the letter on position $K$ .

When he is able to identify the exact type of that kebab, he will stop immediately and eat the kebab.

DSH wants to know the expected moment that he can eat the kebab.

Please output the expected moment multiplied by $N$ .

输入描述:

The input consists of:

One line containing two integers $N,M$ .

Each of the next $N$ lines contains a string $s_i$ of length $M$ , which is the representing string of the $i^{th}$ type.

输出描述:

Output the expected time multiplied by .

示例1

输入

复制

7 7
aaabbbb
aabbbba
dtztxdy
czztxdy
czzyyds
chaoman
fluffyt

输出

复制

说明

For sample 1:

If the kebab DSH got is "aaabbbb":

At moment 1, he knows the first letter is 'a', so the possible types are "aaabbbb" and "aabbbba".

At moment 2, he knows the second letter is 'a', so the possible types are still "aaabbbb" and "aabbbba".

At moment 3, he knows the third letter is 'a', so the type must be "aaabbbb", and he will eat the kebab immediately.

Therefore, the moment he can eat the kebab is 3.

If the kebab DSH got is "aabbbba":

At moment 1, he knows the first letter is 'a', so the possible types are "aaabbbb" and "aabbbba".

At moment 2, he knows the second letter is 'a', so the possible types are still "aaabbbb" and "aabbbba".

At moment 3, he knows the third letter is 'b', so the type must be "aabbbba", and he will eat the kebab immediately.

Therefore, the moment he can eat the kebab is 3.

If the kebab DSH got is "czztxdy":

At moment 1, he knows the first letter is 'c', so the possible types are "chaoman","czzyyds" and "czztxdy".

At moment 2, he knows the second letter is 'z', so the possible types are "czzyyds" and "czztxdy".

At moment 3, he knows the third letter is 'z', so the possible types are "czzyyds" and "czztxdy".

At moment 4, he knows the fourth letter is 't', so the type must be "czztxdy", and he will eat the kebab immediately.

Therefore, the moment he can eat the kebab is 4.

Similarly, we can calculate the answers for other 4 types. The final answer will be

$\frac{3+3+1+4+4+2+1}{7}\cdot 7=18$