Random Line Generator
The process of generating a row is described as follows. The row consists of 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 continue to be added to the row until one of the specified patterns appears as a substring within the row.
Your task is to determine the expected length of the generated row.
Input
The first line contains the integers N and M (1 ≤ N ≤ 8, 1 ≤ M ≤ 10). Here, N represents the number of letters in the alphabet, and M represents the number of patterns. The next M lines each contain a pattern composed of the first N letters of the alphabet. Each pattern has a maximum length of 10.
Output
Print the expected length of the row. An absolute error of no more than 10^{-3} is acceptable.