아드리안

어린 아드리안이 영국의 외딴 곳을 헤매다가 마법사를 만났다. 마법사는 단어가 적힌 종이를 건네며, 그 단어의 부분 문자열 중 글자를 재배열해서 팰린드롬을 만들 수 있는 것의 개수를 세라고 했다. 정확히는 $1 \le i \le j \le$ 단어 길이를 만족하는 인덱스 쌍 $(i, j)$ 중에서, $i$번째부터 $j$번째 글자까지(양 끝 포함)를 재배열해서 팰린드롬으로 만들 수 있는 쌍의 개수를 구하는 것이다. 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같은 단어로, 예를 들어 topot이 그렇다.

첫 줄에 영어 소문자로만 이루어진 단어가 주어진다. 단어의 길이는 최대 1,000,000이다.

조건을 만족하는 부분 문자열의 개수를 한 줄에 출력한다.

두 번째 예제에서 부분 문자열은 t, p, o, o, t, oo, poo(재배열하면 opo가 될 수 있다), oot(재배열하면 oto가 될 수 있다), tpoot(재배열하면 topot이 될 수 있다)이다.