Valerie Pie is interested in something she learned in her combinatorics class called anagrams. An anagram is a rearrangement of letters to form a new word or phrase. The words and phrases don’t need to make sense, but they can. An example anagram is Travis Meade can become Varied Meats. Valerie wants to make anagrams of her name, but she realized that some anagrams contain bad words as substrings. An anagram is forbidden if it contains at least one bad word as a substring. Help Valerie count the number of non-forbidden anagrams of different words for phrases.
Problem Valerie will give a word or phrase, and a list of forbidden words. Compute the number of non-forbidden anagrams.
Input Specification The input will begin with a single non-empty string of at most 12 lower-case, Latin characters, s, representing the phrase, of which Valarie want the anagram count. The next line will contain a single non-negative integer, n (n 20), representing the number of bad words. The remaining n lines will contain one non-empty string of at most 12 lower-case Latin characters. Each of these strings represents a bad word.
Output Specification The output will consist of a single integer, k, representing the number of non-forbidden anagrams of s.