Forbidden Magic Damage

In Magic Land there is a legend: in ancient days, John helped Koishi and her sister Satori to defeat a foe. Later Koishi recovered her mind‐reading ability. Now, however, Koishi faces new trouble on that very island – Flandre Scarlet has arrived with her ability to wield forbidden magic without harm.

To explain the concept of forbidden magic and its damage, we introduce the following definitions. Let \(A\) be an alphabet consisting of the first alphabet lowercase letters. Every nonempty string over \(A\) corresponds to a magic spell. There is a set \(T\) of N strings over \(A\), each of which is called a taboo string (a forbidden pattern).

For any spell (i.e. a string \(s\)) the damage incurred is determined as follows. One may split \(s\) into several segments. For each segment that exactly equals one of the taboo strings the user is harmed. Since the segmentation is chosen optimally, the actual damage is defined as the maximum number of segments (i.e. non‐overlapping occurrences) which can be selected from \(s\) so that each is a taboo string. (Note that if a taboo string \(t\) has a proper prefix that is also taboo then in an optimal segmentation the shorter taboo is chosen – only the minimal taboo strings matter.)

Koishi uses magic at random – it is known that the magic she uses are exactly all strings over \(A\) of length len (each with equal probability). Unfortunately, unlike Flandre Scarlet, she cannot avoid being hurt by forbidden magic. Your task is to compute the expected forbidden‐damage she will suffer on each use. That is, if
\[ E = \frac{1}{|A|^{\text{len}}} \sum_{s\in A^{\text{len}}} \text{damage}(s), \]
compute \(E\).

Input format: The first line contains three integers: alphabet, N and len. Then follow N lines, each containing a nonempty taboo string (over the first alphabet lowercase letters).

Output format: Output a single real number – the expected forbidden damage. Answers within a relative or absolute error of \(10^{-6}\) will be accepted.

Note (on formulation): Since an optimal segmentation will always choose the taboo string with the shortest length when several choices exist (because a taboo string having a taboo proper prefix will never be chosen), the problem reduces to only considering taboo strings that do not have any proper prefix which is also taboo. For each such minimal taboo string of length \(l\), its probability of occurrence (at a fixed starting position) is \(A_l = \frac{\text{(number of minimal taboo strings of length }l)}{\text{ alphabet}^{l}}\). Then, if at a given position the next \(r = \min(\text{len}-i, L_{\max})\) letters are inspected (with \(L_{\max}\) being the maximum length among the minimal taboo strings), the recurrence for the expected damage \(f(i)\) from position \(i\) may be written as:

[ f(i) = \sum_{l=1}^{r} \left( \prod_{j=1}^{l-1}(1-A_j) \right) A_l \Bigl(1+f(i+l)\Bigr) + \left( \prod_{j=1}^{r}(1-A_j) \right) f(i+1), \quad 0 \le i < \text{len}, \quad f(\text{len})=0. ]

Use this recurrence (or an equivalent method) to compute the expected damage.

inputFormat

The input begins with a line containing three integers: alphabet (the number of lowercase letters starting from 'a' that form the alphabet \(A\)), N (the number of taboo strings), and len (the length of the magic spell). Following this, there are N lines, each containing one taboo string.

outputFormat

Output a single real number representing the expected forbidden damage when a spell is chosen uniformly at random among all strings of length len over \(A\). Your answer is considered correct if it has an absolute or relative error of at most \(10^{-6}\).

sample

2 1 3
a

1.500000