Fighting the Heat II

You are back in the bathroom, now solving standard crosswords puzzles. Did you ever think about producing such puzzles? Producing crossword puzzles is surprisingly tedious, especially if one considers that solving crossword puzzles is surprisingly amusing. Fortunately, given a dictionary of words, your computer can help to produce lots of crosswords puzzles. p l a s m a l i c h e n a c h i n g s h i n t o m e n t o r a n g o r a The puzzles we consider are special: frames are n×n empty squares and filled frames are symmetric with respect to the descending diagonal. That is, the i-th “down” word and the i-th “across” word are the same (see above for an example on a 6 × 6 frame). Write a program that reads a list of words from standard input and writes how many puzzles can be produced from those words. Input The input file contains several test cases. The first line of each one contains two integers n (2 ≤ n ≤ 16) and m (1 ≤ m ≤ 20000). Integer n is the frame size while integer m is the number of words in the dictionary. Each of the next m lines contains a word of n letters. Those words are made of the 26 lowercase letters (from ‘a’ to ‘z’) and no word may appear more than once. Output For each input case, the first and only line of the output should contain an integer r, the number of different puzzles that can be made with the words of the list. Notice that a given puzzle may contain a word more than once. Note: The 8 puzzles for the first input case are: aaaa aaaa abab abab aaaa abab baba bbbb aaaa aaaa abab abab aaaa abab baba bbbb baba baba bbbb bbbb aaaa abab baba bbbb baba baba bbbb bbbb aaaa abab baba bbbb

2/2 Sample Input 44 aaaa bbbb abab baba 16 1 abcdefghijklmopq 8 0