하이퍼드롬

어떤 문자열의 문자 위치를 적절히 재배열하여 팰린드롬으로 만들 수 있으면, 그 문자열을 하이퍼드롬이라고 한다.

문자열 $S$가 주어질 때, $S$의 부분 문자열 중 하이퍼드롬인 것의 개수를 구하여라.

$S$의 부분 문자열이란 $i$번째 문자부터 $j$번째 문자까지를 이어 붙인 문자열을 말한다 ($1 \le i \le j \le n$). 부분 문자열의 내용이 같더라도 $(i, j)$가 다르면 서로 다른 부분 문자열로 센다.

문자열 $x_1 x_2 \dots x_l$이 모든 위치 $i$에서 $x_i = x_{l-i+1}$을 만족하면 팰린드롬이라고 한다.

$S$는 알파벳 대문자와 소문자('a'–'z', 'A'–'Z')로 이루어지며, 대문자와 소문자는 서로 다른 문자로 취급한다(예를 들어 'A'와 'a'는 다른 문자다).

첫째 줄에 문자열 $S$의 길이 $n$이 주어진다. ($1 \le n \le 3 \cdot 10^5$)

둘째 줄에 문자열 $S$가 주어진다.

$S$의 부분 문자열 중 하이퍼드롬인 것의 개수를 출력한다.

부분 문자열은 그 자체가 팰린드롬이 아니어도 하이퍼드롬일 수 있다. 예를 들어 'aAA'는 팰린드롬이 아니지만, 재배열하면 팰린드롬 'AaA'가 되므로 하이퍼드롬이다.