Рабочее место участника

Hypergnome planet is famous for its Great Universal Games between gnomes — the Games between gnomes from each part of the galaxy in various disciplines.

The most popular discipline in the Games is the Hyperdrome discipline. The rules are the follows: one string of length n is given to all gnomes. The gnomes shall find, as fast as they can, the total number of Hyperdrome substrings — such strings that characters inside the string can be rearranged to get a palindrome.

Substring is defined as a sequence of characters from position `i` to position `j` inclusive, where `1\ ≤\ i\ ≤\ j\ ≤\ n`. Substrings with different pairs of positions `(i,\ j)` are considered different regardless of their contents. Palindrome is defined as a string `x_1\ x_2\ …\ x_l`, where `x_i\ =\ x_{l-i+1}` for all `1\ ≤\ i\ ≤\ l`.

Judges choose a string and your task is to help them find the answer.

The gnome alphabet consists of lowercase and uppercase English letters — 'a'–'z' and 'A'–'Z' where letters in different case are considered to be different letters.

The first line of the input file contains a single integer `n` (`1\ ≤\ n\ ≤\ 3\ *\ 10^5`). The second line of the input file contains the string for Hyperdrome discipline — `n` lowercase or uppercase English letters.

Output the answer for the Hyperdrome discipline — the number of Hyperdrome substrings in the input string.

3
aaa

6

7
abadaba

12

3
aAA

5

In the first example there are 6 Hyperdrome substrings — (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

In the second example there are 12 Hyperdrome substrings — (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (1, 3), (3, 5), (5, 7), (2, 6), (1, 7).

In the third example there are 5 Hyperdrome substrings — (1, 1), (1, 3), (2, 2), (2, 3), (3, 3). Note, that a Hyperdrome substring (1, 3) is "aAA". It is not a palindrome itself, but its characters can be rearranged to get a palindrome “AaA”