팰린드롬 문장
시간 제한2초메모리 제한128 MB
최대 13개의 서로 다른 단어가 주어질 때, 공백을 지운 문자열이 팰린드롬이 되는 단어 부분집합의 배열 개수를 구하는 문제입니다.
문제
지민이는 서로 다른 단어 N개를 가지고 있다. 이 단어들 중 일부를 골라 한 줄로 배열해 문장을 만들 때, 공백을 모두 제거한 문자열이 팰린드롬이면 그 문장을 팰린드롬 문장이라고 한다.
문장은 하나 이상의 단어로 이루어져야 하며, 인접한 두 단어 사이에는 공백이 하나 들어간다. 각 단어는 한 문장에서 최대 한 번 사용할 수 있다.
공백을 제거한 문자열이 같더라도 단어를 나눈 위치나 순서가 다르면 서로 다른 문장으로 센다. 예를 들어 a ba와 ab a는 서로 다른 문장이다.
만들 수 있는 팰린드롬 문장의 개수를 구하라.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 13)
둘째 줄부터 N개의 줄에 서로 다른 단어가 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있고 길이는 1 이상 13 이하이다.
출력
만들 수 있는 팰린드롬 문장의 개수를 출력한다.