Viruses#2516
In a certain antivirus company, researchers are studying viruses. They know about types of viruses. Each virus is represented by a string of lowercase Latin letters. Different virus types correspond to different strings.
Recently, researchers have started investigating previously unexplored objects — fully infected strings. A string is called fully infected if, for every character in , there exists a substring of that contains this character and is one of the virus strings.
Your task is to find the number of fully infected strings of length given the viruses. Since this number may be very large, output its remainder modulo 10^9+7.
The first line contains two integers and (1 \le n \le 400; 1 \le m \le 20).
Then lines follow, each containing the description of a virus. Each line consists of a sequence of lowercase Latin letters.
The length of each virus is positive and does not exceed characters.
Output a single integer — the remainder of the number of fully infected strings divided by 10^9+7.
Esempio 1