Random Line Generator#3698
The process of generating a string is described as follows. The string consists of a sequence of random characters. Each character is independently selected from the first letters of the Latin alphabet, with each letter having an equal chance of being chosen. Characters continue to be added to the string until one of the specified patterns appears as a substring within the string.
Your task is to determine the expected length of the generated string.
The first line contains the integers and (1 \le N \le 8, 1 \le M \le 10). Here, represents the number of letters in the alphabet, and represents the number of patterns. The next lines each contain a pattern composed of the first letters of the alphabet. Each pattern has a maximum length of .
Print the expected length of the string. An absolute error of no more than 10^{-3} is acceptable.
Example 1