Ice Skating
The Skating Federation has introduced an intriguing new experiment. Instead of traditional starting numbers, athletes will now have starting strings displayed on their suits. This change is intended to enhance the excitement of the competition. These strings will be generated randomly.
Here's how the string generation process works: A string is formed by a sequence of random characters. Each character is independently selected from the first N letters of the Latin alphabet, with each letter having an equal chance of being chosen. Characters are continuously added to the string until one of the specified patterns appears as a substring.
Your task is to determine the expected length of the generated string.
Input
The first line contains two numbers, N and M (1 ≤ N ≤ 8, 1 ≤ M ≤ 10). N represents the number of letters used from the alphabet, while M indicates the number of patterns. The following M lines list the patterns, each composed of the first N letters of the alphabet. The length of each pattern does not exceed 10.
Output
Print the expected length of the string, rounded to two decimal places.