지민이는 단어 N개를 가지고 있고, 이 단어를 이용해서 팰린드롬 문장을 몇 개 만들 수 있는지 알아보려고 한다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 0보다 크다. 문장은 단어로만 구성되어 있고, 각 단어의 사이에는 공백이 한 칸 있다. 문장의 길이는 0보다 커야 한다.</p>

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

몇 개의 팰린드롬 문장을 몇 개 만들 수 있는 지 구해보자. 각 단어는 문장 내에서 최대 1번까지 사용할 수 있고, 두 문장이 공백을 무시했을 때 같아도, 생긴 형태가 다르면 서로 다른 문장이다. 예를 들어 “a ba”와 “ab a”는 다른 문장이다.

입력 형식

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에 각 단어가 주어진다. 각 단어의 길이는 최대 13이고, 중복되지 않는다.

출력 형식

첫째 줄에 단어를 이용해서 만들 수 있는 팰린드롬 문장의 개수를 출력한다.

예제 입력 1

2
a
ba

예제 출력 1

2

예제 입력 2

3
ab
bcd
efg

예제 출력 2

0

예제 입력 3

3
a
bba
abb

예제 출력 3

7

예제 입력 4

10
aabccc
ccbbca
a
acaabb
aaa
aab
c
babb
aacaa
b

예제 출력 4

47