Palindrome Sentences

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.

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.

Print the number of palindrome sentences that can be made.