Ice Skating#748
The Skating Federation has decided to conduct an unusual experiment. Now, instead of starting numbers, athletes will have starting strings displayed on their suits. This change is intended to increase the excitement of the competition. The strings will be generated randomly.
Formally, the generation process is as follows. The string is defined as a sequence of random characters. Each character is independently generated from the first letters of the Latin alphabet with equal probability and appended to the end of the current string. Characters are added to the string until one of the given patterns appears as a substring.
You are required to find the expected length of the generated string.
The first line contains two integers and (1 \leq N \leq 8, 1 \leq M \leq 10). is the number of letters in the alphabet used, and is the number of patterns. Each of the next lines contains a pattern, which is a string of up to characters, composed only of the first letters of the alphabet.
Print the expected length of the string, rounded to two decimal places.
Example 1