Palindrome Pairs

题意翻译

我们希望找到满足以下性质的字符串对$(i,j)$：$s_{i}+s_{j}$的其中一个排列是回文的（如，"aab"和"abcac"的和"aababcac"可以排列为"aabccbaa"，因此这两个串符合要求）。 输入$N$个小写字符串，输出满足要求的对数。**我们认为$(i,j)$和$(j,i)$是同一对。**

题目描述

After learning a lot about space exploration, a little girl named Ana wants to change the subject. Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it: You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa"). Two pairs are considered different if the strings are located on different indices. The pair of strings with indices $ (i,j) $ is considered the same as the pair $ (j,i) $ .

输入输出格式

输入格式

The first line contains a positive integer $ N $ ( $ 1 \le N \le 100\,000 $ ), representing the length of the input array. Eacg of the next $ N $ lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array. The total number of characters in the input array will be less than $ 1\,000\,000 $ .

输出格式

Output one number, representing how many palindrome pairs there are in the array.

输入输出样例

输入样例 #1

3
aa
bb
cd

输出样例 #1

1

输入样例 #2

6
aab
abcac
dffe
ed
aa
aade

输出样例 #2

6

说明

The first example: 1. aa $ + $ bb $ \to $ abba. The second example: 1. aab $ + $ abcac $ = $ aababcac $ \to $ aabccbaa 2. aab $ + $ aa $ = $ aabaa 3. abcac $ + $ aa $ = $ abcacaa $ \to $ aacbcaa 4. dffe $ + $ ed $ = $ dffeed $ \to $ fdeedf 5. dffe $ + $ aade $ = $ dffeaade $ \to $ adfaafde 6. ed $ + $ aade $ = $ edaade $ \to $ aeddea