在了解了很多关于太空探索的知识后,一个名叫安娜的小女孩想要改变话题。
Ana 是一个喜欢回文(可以向后读和向前读一样的字符串)的女孩。她已经学会了如何检查给定的字符串是否是回文,但很快她就厌倦了这个问题,所以她想出了一个更有趣的问题,她需要你的帮助来解决它:
给你一个仅由小写字母组成的字符串数组。你的任务是找出数组中有多少个回文对。回文对是满足以下条件的一对字符串:两个字符串串联的至少一个排列是回文。换句话说,如果你有两个字符串,比如说“aab”和“abcac”,然后将它们连接成“aababcac”,我们必须检查这个新字符串是否存在一个回文排列(在本例中存在排列“aabccbaa”)。
如果字符串位于不同的索引上,则认为两对不同。索引为 $$$(i,j)$$$ 的字符串对被认为与 $$$(j,i)$$$ 相同。
输入
第一行包含一个正整数$$$N$$$ ($$$1 \le N \le 100\,000$$$),表示输入数组的长度。
接下来的 $$$N$$$ 行的每行都包含一个字符串(由从“a”到“z”的小写英文字母组成)——输入数组的一个元素。
输入数组中的字符总数将小于 $$$1\,000\,000$$$。
输出
输出一个数字,代表数组中有多少个回文对。
示例
输入 #1
3 aa bb cd
输出 #1
1
输入 #2
6 aab abcac dffe ed aa aade
输出 #2
6
注意
第一个例子:
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