CF1045I.Palindrome Pairs

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)$.

在学习了大量关于太空探索的知识后，一位名叫安娜的小女孩想要换一个主题。

安娜是一位热爱回文串（即正读和反读都相同的字符串）的女孩。她已经学会了如何判断一个给定字符串是否为回文串，但很快她就对这个问题感到厌倦了，于是提出了一个更有趣的问题，并需要你的帮助来解决它：

给你一个仅由小写字母组成的字符串数组。你的任务是找出该数组中回文对的数量。所谓回文对，是指满足如下条件的一对字符串：这两个字符串拼接后所得字符串的至少一种排列是回文串。换句话说，如果你有两个字符串，例如 "aab" 和 "abcac"，将它们拼接成 "aababcac"，我们需要判断是否存在该新字符串的一个排列，使其构成回文串（本例中存在排列 "aabccbaa"）。

若两个字符串位于不同下标位置，则视为不同的对；而下标对 $(i,j)$ 与 $(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$.

第一行包含一个正整数 $N$（$1 \le N \le 100\,000$），表示输入数组的长度。

接下来的 $N$ 行，每行包含一个字符串（由小写英文字母 'a' 到 'z' 组成）——即输入数组的一个元素。

输入数组中所有字符的总数少于 $1\,000\,000$。

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

输出一个数字，表示数组中回文对的数量。

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

第一个例子：

1. aa $+$ bb $\to$ abba。

第二个例子：

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