该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个长度为$\red{n}$的仅包含大小写字母的字符串，请问它有多少个子串经过重新排列后为可以变成回文串。

输入格式

第一行输入一个正整数$\red{n}$；

第二行输入一个长度为$\red{n}$的字符串，且保证仅包含大小写字母。

输出格式

输出一个整数表示答案。

样例

输入样例1

3
AAA

输出样例1

6

输入样例2

7
ABADABA

输出样例2

12

输入样例3

3
Aaa

输出样例3

5

提示

对于$\red{100\%}$的数据满足$\red{1<=n<=3\times 10^5}$

其中$\red{40\%}$的数据满足$\red{1<=n<=100}$