정사각형 크로스워드
시간 제한1초메모리 제한128 MB
길이가 같은 단어들 중 네 개를 골라 정사각형 크로스워드의 위아래, 좌우 단어와 모서리 글자가 맞도록 배치하는 경우의 수를 구합니다.
문제
상근이는 전 세계에 있는 크로스워드 퍼즐을 모두 풀었다. 더 이상 풀 퍼즐이 없어서 직접 새로운 퍼즐을 만들려고 한다.
길이가 같은 네 단어를 사용하면 정사각형 모양의 크로스워드 퍼즐을 만들 수 있다. 위쪽과 아래쪽에 놓인 단어는 왼쪽에서 오른쪽으로 읽고, 왼쪽과 오른쪽에 놓인 단어는 위에서 아래로 읽는다. 아래 그림은 "HLAD", "NIVA", "HSIN", "DEDA"를 사용해 만든 퍼즐 하나이다.
길이가 모두 같은 여러 단어가 주어졌을 때, 만들 수 있는 서로 다른 정사각형 크로스워드 퍼즐의 개수를 구하라. 하나의 퍼즐에서 같은 단어를 두 번 사용할 수 없다. 두 퍼즐이 적어도 한 칸에서 서로 다른 문자를 가진다면 서로 다른 퍼즐로 본다.
입력
첫째 줄에 단어의 개수 N이 주어진다. (4 ≤ N ≤ 100,000)
다음 N개 줄에는 알파벳 대문자로만 이루어진 단어가 한 줄에 하나씩 주어진다. 모든 단어의 길이는 같고, 길이는 10 이하이다. 입력으로 주어지는 모든 단어는 서로 다르다.
출력
입력으로 주어진 단어들을 사용해 만들 수 있는 서로 다른 정사각형 크로스워드 퍼즐의 개수를 출력한다.