Palindrome Sentences

Time limit2sMemory limit128 MB

Summary

Given up to 13 distinct words, count ordered arrangements of a subset of them whose concatenation without spaces forms a palindrome.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, String, String matching
Solved: No attempts yet

Problem

Jimin has N distinct words. A sentence is made by choosing some of these words and arranging them in one line. If the string obtained by removing all spaces is a palindrome, the sentence is called a palindrome sentence.

A sentence must contain at least one word, and there is exactly one space between two adjacent words. Each word can be used at most once in a sentence.

Even if two sentences become the same string after spaces are removed, they are counted as different when the word boundaries or the word order are different. For instance, a ba and ab a are different sentences.

Find the number of palindrome sentences that can be made.

Input

The first line contains the number of words N. (1 ≤ N ≤ 13)

Each of the next N lines contains one distinct word. Every word consists only of lowercase English letters and has length between 1 and 13, inclusive.

Output

Print the number of palindrome sentences that can be made.

Examples4

Example 1
Input
```
2
a
ba
```
Expected output
```
2
```
Example 2
Input
```
3
ab
bcd
efg
```
Expected output
```
0
```
Example 3
Input
```
3
a
bba
abb
```
Expected output
```
7
```

Example 4

Input

10
aabccc
ccbbca
a
acaabb
aaa
aab
c
babb
aacaa
b

Expected output