이중 회문

바냐는 회문을 만드는 공장에서 일한다. 공장에는 길이가 $n$인 소문자 영어 알파벳 문자열 $s$로 된 가공품이 있고, 바냐는 여기서 임의의 부분 문자열을 잘라 판매할 수 있다. 회문은 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.

많은 사람이 평범한 회문에 질렸기 때문에, 바냐는 대신 이중 회문을 만들기로 했다. 이중 회문은 길이가 같은 회문 두 개를 이어 붙인 문자열이다. 예를 들어 aabb와 aaaa는 이중 회문이지만, abba와 aaaabb는 이중 회문이 아니다.

바냐는 $s$에서 이중 회문을 잘라내는 방법이 몇 가지인지 궁금해한다. 즉, 부분 문자열 $s_l s_{l+1} \ldots s_r$이 이중 회문이 되는 쌍 $(l, r)$의 개수를 구하라.

첫 줄에 문자열의 길이 $n$ ($1 \leq n \leq 500\,000$)이 주어진다. 둘째 줄에는 소문자 영어 알파벳으로 이루어진 문자열 $s$가 주어진다.

이중 회문인 부분 문자열의 개수를 한 줄에 출력한다.

첫 번째 예제에서 길이 2인 이중 회문은 ab, ba, ac, ca, ac로 5개이다. 문자열 전체인 abacac도 이중 회문이다.