Maximum Distinct Usernames

You are given a username length \(n\) and a list of forbidden substrings. A valid username is a string of length \(n\) consisting of characters from the set abcdefghijklmnopqrstuvwxyz0123456789 (36 characters in total) that does not contain any of the forbidden substrings as a consecutive block.

Your task is to compute the total number of valid usernames. The input contains several test cases and is terminated by a line with two zeros (0 0). For each test case, first the integers \(n\) and \(m\) are given, where \(n\) is the length of the username and \(m\) is the number of forbidden substrings. This is followed by \(m\) lines, each containing one forbidden substring.

Note: Because checking each possible username by brute force may be inefficient for larger \(n\), you should use an efficient algorithm such as dynamic programming combined with the Aho–Corasick automaton to filter out strings that include any forbidden substring.

The answer for each test case is a single integer denoting the count of valid usernames, calculated exactly.

inputFormat

The input consists of multiple test cases. Each test case begins with a line containing two integers \(n\) and \(m\) separated by a space, where:

• \(n\) is the length of the username.
• \(m\) is the number of forbidden substrings.

This is followed by \(m\) lines, each containing a forbidden substring. The input is terminated by a line containing "0 0" which should not be processed.

Input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer which is the number of valid usernames of length \(n\) that do not contain any forbidden substring.

Output should be written to standard output (stdout).

## sample

3 0
0 0

46656

</p>