#1570 Palindrome Phrases

10 s   128 MB  

Description


One of your friends has given you several words and asked you how many palindromic phrases you can compose with those words. To save yourself some time, you've decided to write a program to answer this question. In this problem, a word is defined as a non-empty sequence of lowercase letters ('a'-'z'). A phrase is a non-empty sequence of words, where each pair of consecutive words is separated with exactly one space character. A phrase is palindromic if it reads the same forward and backward, ignoring space characters.

Compute the number of different palindromic phrases that can be composed with the given words. Each word can be used at most once within each phrase. Two phrases are considered different if they are different strings, even if they read the same when ignoring spaces (for example, "a ba" and "ab a" are different phrases).

Input

Input consists of multiple test cases. Input is terminated by EOF.

For each test case, the first line contains a single integer N, the number of words. N is at most 13.

The following line contains exactly N words composed by lowercase alphabet letters (‘a’-’z’). Each word contains at most 13 letters, and all words given will be distinct.

Output

For each test case, write a single line which contains the number of different palindromic phrases that can be composed with the given words. Note that this integer may not fit in 32-bit integer type.

Sample Input

Sample Output

2
a ba
3
ab bcd efg
3
a bba abb
2
0
7

HINT

For the third case of sample input, note that we have 7 different palindromic phrases :

"a", "a bba", "abb a", "abb bba", "bba abb", "abb a bba", "bba a abb"


Note that even though "a bba" and "abb a" represent the same palindrome, they differ as strings, so we count both of them.

Source

SRM 439