Description

People in Magic Land always mention the legend: their ancestor John helped Koishi and her elder sister Satori on that eastern island, and they ultimately fought to a draw. After that, Koishi recovered her mind-reading ability...

Now, in an age when John has become a legend, people who revisit that island find that Koishi has run into new trouble.

This time she encounters Flandre Scarlet — she has the ability to use taboo magic without being harmed.

To explain what taboo magic is and how it causes damage, we introduce the following concepts:

1. Every non-empty string over an alphabet $A$ corresponds to a spell. Here $A$ is the set containing the first $alphabet$ lowercase letters.
2. There is a set $T$ that contains $N$ strings over the alphabet $A$. Each string in $T$ is called a taboo string (taboo string).
3. A spell, or equivalently its corresponding string $s$, causes damage to the user due to taboos as follows: partition $s$ into several segments, and consider the number of segments that are taboo strings. Different partitions may yield different counts; the maximum count is the damage.

Because she can read minds, Koishi always uses Flandre Scarlet’s spells at random. Concretely, her spells correspond exactly to all strings of length $len$ over the alphabet $A$.

However, some of Flandre Scarlet’s spells are taboo. Due to her special nature, she can use taboo magic without taking damage, but Koishi cannot. Poor Koishi faces the threat of taboo damage every time she uses one of Flandre’s spells.

You need to compute the expected taboo damage when Koishi picks each of Flandre’s spells with equal probability, i.e., uniformly over all length-$len$ strings over $A$.

Input Format

The first line contains three positive integers $N$, $len$, $alphabet$.
The next $N$ lines each contain a string $T_i$, representing a taboo string.

Output Format

Output a non-negative real number, the expected taboo damage. Your answer must have an absolute error not exceeding $10^{-6}$.

2 4 2
aa
abb

0.75

Hint

[Explanation for Sample 1]
There are $2^4 = 16$ different spells.

Note that the taboo damage of "aabb" is 1 rather than 2.

Constraints

• In at least 40% of the testdata: $N = 1$.
• For 100% of the testdata: $N \le 5$, $len \le 10^9$, $1 \le alphabet \le 26$.
• The testdata guarantees that the length of each string $T_i$ does not exceed $15$, and is non-empty.
• The testdata guarantees that each $T_i$ contains only the first $alphabet$ lowercase letters.
• The testdata guarantees that the set $T$ has no duplicate elements; that is, for any distinct $i$ and $j$, $T_i \ne T_j$.

Translated by ChatGPT 5