cho.shSquare Crossword
Time limit1sMemory limit128 MBProblem
Sanggeun has solved every crossword puzzle in the world. Since there are no puzzles left to solve, he wants to make a new one.
Using four words of the same length, it is possible to make a square crossword puzzle. The words placed on the top and bottom are read from left to right, and the words placed on the left and right are read from top to bottom. The grid below is one puzzle made with "HLAD", "NIVA", "HSIN", and "DEDA".
| H | L | A | D |
| S | E | ||
| I | D | ||
| N | I | V | A |
Given several words that all have the same length, count how many different square crossword puzzles can be made. The same word cannot be used twice in one puzzle. Two puzzles are considered different if at least one cell contains a different letter.
Input
The first line contains the number of words N. (4 ≤ N ≤ 100,000)
Each of the next N lines contains one word consisting only of uppercase English letters. All words have the same length, and that length is at most 10. All input words are distinct.
Output
Print the number of different square crossword puzzles that can be made using the given words.