시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 78 16 13 32.500%

문제

지민이와 그의 친구는 단어를 N개 가지고 있다. 그리고 이 단어를 적절히 조합해서 팰린드롬 문장을 몇 개 만들 수 있을 지 궁금해졌다.

단어는 알파벳 소문자로만 이루어져 있고, 길이가 0은 아니다.

문장은 단어들로만 구성되어 있고, 각 단어 사이에는 공백이 한 칸 있으며, 길이가 0이 아니다.

팰린드롬 문장은 공백을 무시했을 때, 앞에서부터 읽을 때와 뒤에서부터 읽을 때가 같은 것이다.

단어가 주어질 때, 이 단어를 가지고 팰린드롬 문장을 몇 개 만들 수 있는 지 구하는 프로그램을 작성하시오. 각 단어는 문장 내에서 최대 1번까지 사용될 수 있고, 두 문장이 공백을 무시하고 같게 읽혀도, 생긴 것이 다르면 서로 다른 문장으로 친다. 예를 들어 “a ba”와 “ab a”는 다른 문장이다.
 

입력

첫째 줄에 단어의 개수 N이 주어진다. 단어의 개수는 13보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 각 단어의 길이는 최대 13이다. 단어는 중복되지 않는다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

2
a
ba

예제 출력

2

힌트

출처