Description

It is well known that passwords play an invaluable role in the field of information. For ordinary login passwords, the only way to crack them is brute force—trying all possible letter combinations one by one—but this is time-consuming and easy to detect. Therefore, before attempting a brute-force attack, one must do a lot of preparation. After gathering intelligence, we have obtained several useful pieces of information of the form:

"I observed that the password contains the string *."

For example, for a password of length $10$ and the observed substrings hello and world, possible passwords are helloworld and worldhello. For a password of length $6$ and the observed substrings good and day, a possible password is gooday.

With such information, the number of attempts can be greatly reduced. Please write a program to compute all possible passwords. The password may contain only lowercase letters in a-z.

Input Format

The input begins with two integers $L, N$, denoting the password length and the number of observed substrings, respectively.

Then follow $N$ lines, each containing a string that describes one observed substring.

Output Format

The first line of the output contains a single integer: the total number of passwords that contain all observed substrings.

If this number is less than or equal to $42$, output all possible passwords in lexicographical order, one per line. Otherwise, output only the total count.

10 2
hello
world

2
helloworld
worldhello

Hint

Constraints: For $100\%$ of the testdata, $1 \le L \le 25$, $1 \le N \le 10$, each observed substring has length at most $10$, and it is guaranteed that the output is less than $2^{63}$.

Translated by ChatGPT 5