题目描述

ztm 最近刚刚学习了动态规划，其中一道题是问：给定一个字符串，问最少需要添加几个字符可以使得它变成一个回文字符串

ztm 经过自己的思考，想到了一个有趣的改动

如果给定一个字符串，直接询问这个字符串中有多少个子串在经过重新排列后可以成为回文串呢？

P.S. 即直接拿出一个子串，若这个子串的字符经过任意重新排列后可以成为一个回文串，则认为这个子串是符合要求的

输入格式

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

输出格式

输出一个整数表示答案。

数据范围

对于 $40\%$ 的数据满足： $1 \leq n \leq 100$ 对于 $100\%$ 的数据满足： $1 \leq n \leq 3 * 10^5$

样例输入

7
ABADABA

样例输出

12