하이퍼드롬

문자열이 주어졌을 때, 이 문자열에 포함된 문자의 위치를 적절히 바꿔서 팰린드롬으로 만들 수 있을 때, 그 문자열을 하이퍼드롬이라고 한다.

문자열 S가 주어졌을 때, 그 문자열의 부분 문자열 중 하이퍼드롬의 개수를 구하는 프로그램을 작성하시오.

문자열의 부분 문자열이란, 문자열의 i번째부터 j번째까지 문자로 이루어진 문자열을 말한다. (1 ≤ i ≤ j ≤ n) 이때, 부분 문자열이 같더라도 (i, j)가 다르다면 다른 부분 문자열이다.

x1,x2,...,xl로 이루어진 문자열이 모든 위치 i에서 xi = xl-i+1을 만족할 때, 팰린드롬이라고 한다.

문자열은 알파벳 대소문자로 이루어져 있고, ('a'-'z', 'A'-'Z') 대문자와 소문자는 다른 문자로 생각하면 된다. (A와 a는 다른 문자다)

첫째 줄에 S의 크기 n이 주어진다. (1 ≤ n ≤ 3·105)

둘째 줄에는 S가 주어진다.

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

첫 번쨰 예제의 경우에 6개의 하이퍼드롬이 있다. - (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

두 번째 예제의 경우에는 12개가 있다. - (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (1, 3), (3, 5), (5, 7), (2, 6), (1, 7)

세 번째 예제의 경우에는 5개의 하이퍼드롬 부분문자열이 있다. - (1, 1), (1, 3), (2, 2), (2, 3), (3, 4). 부분문자열 (1, 3) "aAA" 는 하이퍼드롬이다. 이 문자열은 팰린드롬이 아니지만, 재배열해서 "AaA"를 만들 수 있기 때문이다.