팰린드롬 문장

지민이는 서로 다른 단어 N개를 가지고 있다. 이 단어들 중 일부를 골라 한 줄로 배열해 문장을 만들 때, 공백을 모두 제거한 문자열이 팰린드롬이면 그 문장을 팰린드롬 문장이라고 한다.

문장은 하나 이상의 단어로 이루어져야 하며, 인접한 두 단어 사이에는 공백이 하나 들어간다. 각 단어는 한 문장에서 최대 한 번 사용할 수 있다.

공백을 제거한 문자열이 같더라도 단어를 나눈 위치나 순서가 다르면 서로 다른 문장으로 센다. 예를 들어 a ba와 ab a는 서로 다른 문장이다.

만들 수 있는 팰린드롬 문장의 개수를 구하라.

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 13)

둘째 줄부터 N개의 줄에 서로 다른 단어가 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있고 길이는 1 이상 13 이하이다.

만들 수 있는 팰린드롬 문장의 개수를 출력한다.